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

не все графы являются планарными.
В трехмерном пространстве можно геометрически реализовать без пересечения ребер любой граф.
Слайд 3Планарные графы
На рисунке приведен пример не планарного графа
Рис. 1 Граф «три

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

Слайд 5Изоморфные графы
Рис.2. Изоморфные графы

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

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

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

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

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

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

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