Слайд 2Планарные графы
- Это графы, допускающие геометрическую реализацию на плоскости без пересечения ребер.
Далеко
![Планарные графы - Это графы, допускающие геометрическую реализацию на плоскости без пересечения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-1.jpg)
не все графы являются планарными.
В трехмерном пространстве можно геометрически реализовать без пересечения ребер любой граф.
Слайд 3Планарные графы
На рисунке приведен пример не планарного графа
Рис. 1 Граф «три
![Планарные графы На рисунке приведен пример не планарного графа Рис. 1 Граф](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-2.jpg)
дома - три колодца»
Слайд 4Изоморфные графы
Графы, отличающиеся только нумерацией вершин, называются изоморфными.
![Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-3.jpg)
Слайд 5Изоморфные графы
Рис.2. Изоморфные графы
![Изоморфные графы Рис.2. Изоморфные графы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-4.jpg)
Слайд 6Пустой и полный граф
Граф называется пустым, если множество ребер пусто.
Рис. 3. Пустой
![Пустой и полный граф Граф называется пустым, если множество ребер пусто. Рис. 3. Пустой граф](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-5.jpg)
граф
Слайд 7Пустой и полный граф
Граф называется полным, если любые две вершины связаны ребром.
![Пустой и полный граф Граф называется полным, если любые две вершины связаны](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-6.jpg)
Рис. 4. Полный
граф
Слайд 8Двудольный граф граф
Граф называется двудольным если множество его ребер разбито на два
![Двудольный граф граф Граф называется двудольным если множество его ребер разбито на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-7.jpg)
подмножества,
и ребрами связаны только вершины из разных подмножеств.
Слайд 9Двудольный граф граф
Рис. 5. Двудольный
граф
![Двудольный граф граф Рис. 5. Двудольный граф](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-8.jpg)
Слайд 10Двудольный граф граф
Граф называется полным двудольным, если каждая
вершина
Связана ребром
с
![Двудольный граф граф Граф называется полным двудольным, если каждая вершина Связана ребром](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-9.jpg)
каждой
вершиной
Рис. 6. Полный
двудольный граф
Слайд 11Двудольный граф граф
Если , а , то полный двудольный граф обозначается:
![Двудольный граф граф Если , а , то полный двудольный граф обозначается:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-10.jpg)
Слайд 12Двудольный граф граф
Пример двудольного
графа
![Двудольный граф граф Пример двудольного графа](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1167091/slide-11.jpg)