Какие бывают графы

Содержание

Слайд 2

Планарные графы

- Это графы, допускающие геометрическую реализацию на плоскости без пересечения ребер.
Далеко

Планарные графы - Это графы, допускающие геометрическую реализацию на плоскости без пересечения
не все графы являются планарными.
В трехмерном пространстве можно геометрически реализовать без пересечения ребер любой граф.

Слайд 3

Планарные графы

На рисунке приведен пример не планарного графа
Рис. 1 Граф «три

Планарные графы На рисунке приведен пример не планарного графа Рис. 1 Граф
дома - три колодца»

Слайд 4

Изоморфные графы

Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Слайд 5

Изоморфные графы
Рис.2. Изоморфные графы

Изоморфные графы Рис.2. Изоморфные графы

Слайд 6

Пустой и полный граф

Граф называется пустым, если множество ребер пусто.
Рис. 3. Пустой

Пустой и полный граф Граф называется пустым, если множество ребер пусто. Рис. 3. Пустой граф

граф

Слайд 7

Пустой и полный граф

Граф называется полным, если любые две вершины связаны ребром.

Пустой и полный граф Граф называется полным, если любые две вершины связаны

Рис. 4. Полный
граф

Слайд 8

Двудольный граф граф

Граф называется двудольным если множество его ребер разбито на два

Двудольный граф граф Граф называется двудольным если множество его ребер разбито на
подмножества,
и ребрами связаны только вершины из разных подмножеств.

Слайд 9

Двудольный граф граф
Рис. 5. Двудольный
граф

Двудольный граф граф Рис. 5. Двудольный граф

Слайд 10

Двудольный граф граф

Граф называется полным двудольным, если каждая
вершина
Связана ребром
с

Двудольный граф граф Граф называется полным двудольным, если каждая вершина Связана ребром
каждой
вершиной
Рис. 6. Полный
двудольный граф

Слайд 11

Двудольный граф граф
Если , а , то полный двудольный граф обозначается:

Двудольный граф граф Если , а , то полный двудольный граф обозначается:

Слайд 12

Двудольный граф граф

Пример двудольного
графа

Двудольный граф граф Пример двудольного графа