Информатика на Python, семестр 2, лекция 3, ФБВТ МФТИ (2024)
Вставка
- Опубліковано 16 чер 2024
- 2 семестр, лекция 3: Теория графов
Таймкоды:
00:00 Приветствие
00:40 Задача о кенигсбергкских мостах
3:10 Определения в теории графов
45:17 Изоморфизм графов
48:40 Матрица смежности
Плейлист с лекциями 1-го курса ФБВТ МФТИ: • 2023 ФБВТ Информатика ...
Снял и смонтировал видео: youtube.com/@antonoreshkin?si...
Тимофей Федорович, рад вас видеть. С Богом!!!
Здравствуйте!
Тайм-коды\конспект по лекции №3:
0:00 задачка Эйлера
3:00 упрощаем рисунок
6:00 на самом деле ребра и за ними закреплены пары верщин
7:20 Индифферентно
8:00 граф является математической моделью соц. сетей
9:00 пример с бесконечным количеством вершин или ребер
10:20 еще важный момент
10:50 про изолированные вершины
12:30 степень вершины - это количество инцидентных ей ребер
14:00 Мост- петля, что если?
14:30 простой граф (без петель и кратных ребер)
15:30 пустой граф существует.
16:20 делаем последовательность подграфов
17:30 что произошло? У нового графа понизилась степень
20:00 итог. Обратите внимание. Путь - это есть..., простой путь - это...
23:20 простой путь Эйлера
24:50 цикл Эйлера
25:50 интересный момент, рисуем новый граф
37:30 граф называется связным
28:30 пример соц. сетей
31:30 сколько ориентаций у графа
32:20 обратите внимание ориентаций возможно...
33:00 связный граф
34:30 слабосвязный оргграф
35:20 выделяем подграфы, которые будут...компонента связности
37:10 минимальная компонента связности
38:30 смотрим вершину В
39:20 сильная связности
41:05 элементарный путь - это
42:20 рисуем вот такой граф, простой...
43:00 задачка Эйлера
45:20 изоморфизм графов
48:00 обратите внимание для оргграфов у меня всё сложнее
52:10 после матрицы смежности показываю вам интересную штуку
53:00 переименовываем вершины, сколько вариантов перестановок существует?
55:30 графы топологически равны друг-другу. Изоморфизм
56:40 пример Графа
58:00 как найти изоморфизм?
58:40 маленькая хитрость (степени вершин просчитать)
59:50 соответственно определяем вершины
1:01:40 правда возникает вопрос...
1:03:10 представьте, что я матрицу храню в списке списков (без букв)
1:03:50 проверка смежности происходит за О(1)
1:04:30 вариант с идентификаторами
1:05:30 делаем словарь
1:07:10 Отказаться от идентификаторов вообще не проблемами все вершины переиндексировать
1:08:10 хотелось бы заранее иметь список смежности
1:10:10 про граф в котором каждая вершина связана с каждой...--> Полный граф
1:11:00 клики это
1:11:10 дописываем списки смежности
1:12:10 в такой форме удобно хранить разные ориентированные, неориентированные графы
Успехов в обучении и мирного неба над головой!
Благодарю, очень познавательно!
Спасибо.
Спасибо ❤
👍
Как попасть на учебу? Где вы преподаёте?
А когда 4я лекция выйдет?
Интересно, я понял как решать такие задачи, откуда начинать путь, но пока, посмотрев половину, не понял, причем тут информатика, и с ориентацией пока сложно понимается
Еще странно, что ошибку так поздно заметили
А ещё я не понял к чему это всё
Воспитываете новое поколение солдат
Это является какой-то проблемой?
Солдаты, обычно, лекций не посещают…
А что не так с солдатами?😂