Комбинаторика
<<  Более сложные задачи по комбинаторике Комбинаторика  >>
Определение графа
Определение графа
Определение графа
Определение графа
Дерево
Дерево
Обход дерева в ширину
Обход дерева в ширину
Обход дерева в глубину
Обход дерева в глубину
Остовное дерево графа
Остовное дерево графа
Топологическая сортировка
Топологическая сортировка
Двусвязные компоненты
Двусвязные компоненты
Поиск точек сочленения
Поиск точек сочленения
Картинки из презентации «Краткое введение в теорию графов» к уроку алгебры на тему «Комбинаторика»

Автор: iceslice. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Краткое введение в теорию графов.ppt» со всеми картинками в zip-архиве размером 212 КБ.

Краткое введение в теорию графов

содержание презентации «Краткое введение в теорию графов.ppt»
Сл Текст Сл Текст
1Краткое введение в теорию графов. 6его вершины Деревья поиска в ширину и
Салищев С. И. глубину – остовные Хорда – ребро графа не
2Определение графа. Ориентированный из остовного дерева.
Граф. Вершина. Дуга. Неориентированный 7Классификация ребер при поиске в
Граф. Ребро. глубину. Ребра дерева Прямые ребра
3Дерево. Дерево – связный соединяют вершину с потомком в дереве
неориентированный ациклический граф Обратные ребра соединяют вершину с предком
Корневое дерево – дерево с выделенной в дереве Перекрестные ребра – остальные
вершиной (корнем), корень задает ребра В неориентированном графе все ребра
ориентацию Ориентированное дерево – не в дереве - обратные.
связный ориентированный граф в котором все 8Топологическая сортировка.
вершины кроме одной имеют входящую степень Топологическая сортировка упорядочивает
1, одна вершина (корень) имеет входящую вершины ориентированного графа в порядке
степень 0 Лист – вершина с исходящей не нарушающем направление дуг Обратный
степенью 0 Лес – множество деревьев. порядок завершения при поиске в глубину
4Обход дерева в ширину. Порядок дает топологическую сортировку Граф имеет
посещения вершин по слоям BFS(start_node, цикл если поиск в глубину находит обратное
goal_node) { // изначально список ребро Порядок обхода в ширину дает
посещённых узлов пуст for(all nodes i) { топологическую сортировку (следует
visited[i] = false;} добавить виртуальную вершину для
queue.push(start_node); // начиная с объединения истоков).
узла-источника visited[start_node] = true; 9Двусвязные компоненты. Точка
while(! queue.empty() ) { // пока очередь сочленения (шарнир) – вершина, удаление
не пуста node = queue.pop(); // извлечь которой из графа делает его несвязным
первый элемент в очереди if(node == Двусвязный граф – не содержащий точек
goal_node) { // проверить, не является ли сочленения Двусвязная компонента –
текущий узел целевым return true;} // все максимальный двусвязный подграф Мост –
преемники текущего узла, ... foreach(child ребро при удалении нарушающее связность
in expand(node)) { // ... которые ещё не графа Мост – двусвязная компонента из
были посещены ... if(visited[child] == одного ребра Граф разбивается на множество
false) { queue.push(child); // ... двусвязных компонент, разделенных точками
добавить в конец очереди... visited[child] сочленения Двусвязные компоненты образуют
= true; // ... и пометить как посещённые } дерево.
} } return false; // Целевой узел 10Поиск точек сочленения. Поиск в
недостижим }. глубину не находит обратных ребер между
5Обход дерева в глубину. 1 procedure двусвязными компонентами Пусть вершины
DFS(G,v): 2 label v as discovered 3 for занумерованы временем обнаружения при
all edges e in G.adjacentEdges(v) do 4 if поиске в глубину d(v) Для каждой вершины
edge e is unexplored then 5 w ? найдем L(v) – минимальный номер вершины, в
G.adjacentVertex(v,e) 6 if vertex w is которую можно вернуться по обратному ребру
unexplored then 7 label e as a discovered из v или потомков v или номер родителя,
edge 8 recursively call DFS(G,w) 9 else 10 если обратных ребер нет v является точкой
label e as a back edge 11 label v as сочленения тогда и только тогда Корень,
explored. Посещение вершин по правилу если у него больше одного ребенка Другие
левой руки Время обнаружения и время вершины, если есть ребенок u и L(u)=d(v)
завершения образуют правильную скобочную Пример: (4, 2), (5, 2) – обратные ребра
последовательность – любые два интервала L(2)=1, L(3)=2, L(4)=2, L(5)=2, L(6)=5 2,
либо не пересекаются либо один содержится 5 – точки сочленения (1, 2), (5, 6) –
в другом. мосты [(2, 3), (3, 4), (4, 5), (4, 2), (5,
6Остовное дерево графа. Поддерево (лес) 2)] – двусвязная компонента.
неориентированного графа, содержащее все
Краткое введение в теорию графов.ppt
http://900igr.net/kartinka/algebra/kratkoe-vvedenie-v-teoriju-grafov-61158.html
cсылка на страницу

Краткое введение в теорию графов

другие презентации на тему «Краткое введение в теорию графов»

«Теории кислот и оснований» - Увеличение кислотности. Увеличение стабильности аниона (сопряженного основания). Данный тип реакций обозначают буквой S (от английского слова "замещение" - substitution). Субстрат – молекула, на которую воздействуют во время реакции. Например, какая кислота сильнее уксусная (СН3СООН или хлоруксусная ClCH2COOH?

«Теории мотивации» - Введение в теории мотивации. Мотив. Мотивация – внутренний процесс, приводящий к поведению, направленному на удовлетворение потребности. Потребность в причастности, соучастии. Теории мотивации. Пирамида потребностей Маслоу Теория потребностей МакКлелланда. Ценность результата для конкретного индивида.

«Теория жизни» - У Демокрита начало жизни было в иле, у Фалеса – в воде, у Анаксагора – в воздухе. Древний Египет. Спонтанное зарождение жизни: Возникновение жизни. Креационизм. С идеей вечного существования жизни во Вселенной связана и следующая группа гипотез. Наиболее распространен креационизм был в Древней Греции и Древнем Египте.

«Теория игр» - Итеративный метод Брауна – Робинсона. План лекции. Может ли у матрицы быть несколько седловых точек? Смешанные стратегии. Матричные игры. Пусть игрок 1 имеет всего m стратегий, а игрок 2 – n стратегий. Тогда игра Г полностью задается матрицей ,где. Алгоритмы теории игр. Основное применение теории игр – – экономика.

«Граф» - Султана 05.05.1939. Одним росчерком. Графом является и система улиц города. Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. Вершина графа. Сурайа. На рисунке приведена часть генеалогического дерева знаменитого дворянского рода Л. Н. Толстого. Задача: Аркадий, Борис. Карпов Михаил 29.10.1935.

«Теория света» - Как называется раздел физики, изучающий природу и свойства света? U ср< Uвак всегда. Что такое корпускулярно-волновой дуализм? Закрепление Предложите модель искусственного источника света, используя подручные средства. Что такое корпускулярно – волновой дуализм? Домашнее задание Различные взгляды на природу света.

Комбинаторика

25 презентаций о комбинаторике
Урок

Алгебра

35 тем
Картинки
900igr.net > Презентации по алгебре > Комбинаторика > Краткое введение в теорию графов