тонова графами назіваються графі, утворені вершинами и ребрами п'яти правильних многогранніків - Платонових тіл: тетраедра, куба, октаедра, додекаедра та ікосаедра.
Граф До 4 , збережений на рис. 1.3.1, відповідає тетраедру, а графи, что відповідають кубу и октаедру, показані на рис. 1.3.3.1 відповідно.
Рис. 1.3.3.1 Платонові графі
Двочастінні графі
Означення 1.3.4.1 Граф назівається двочастіннім, ЯКЩО існує таке розбіття множини его вершин на два класи, при якому кінці шкірного ребра лежати у різніх класах.
Означення двочастінного графа можна податі іншім чином - в термінах розфарбування его вершин двома Кольорах, Наприклад червоним и сінім. При цьом граф назівається двочастіннім, ЯКЩО шкірно его вершину можна пофарбуваті сінім або червоного кольору, так щоб Кожне его ребро мало один Кінець червоний, а другий - синій. p align="justify"> Если в двочастінному графі будь-які Дві вершини з різніх класів суміжні, то такий граф назівається ПОВНЕ двочастіннім графом. Повний двочастінній граф, в Якого один клас має m вершин, а другий n - вершин позначають До m, n
Повний двочастінній граф До 1, n назівається зірковім графом. На рис. 1.3.4.1 збережений граф К 1,5.
В
Рис. 1.3.4.1 Зірковий граф
Аналогічно можна ввести k-частинні графі. Граф назівається k-Частинами графом, ЯКЩО існує таке розбіття множини его вершин на k класів, при якому будь-яке ребро графа з'єднує Дві вершини з різніх класів.
.4 маршрутів, ланцюги и циклі
Маршрутом в графі назівається скінченна послідовність суміжніх ребер. Кожне ребро маршрут.
Число ребер у маршруті назівається Довжина маршруту .
Маршрут у Якого ВСІ ребра Різні назівається Ланцюг .
Циклом в графі Прийнято назіваті послідовність вершин, шкірних пара якіх є кінцямі одного ребра, а решта вершин (і ребра) НЕ повторюється. Іншімі словами, цикл - це замкнутому маршруту, что проходити через шкірні свою вершину и ребро Тільки один раз.
Маршрут (цикл) у Якого ВСІ ребра Різні назівається пробачимо.
Відстанню від вершини А до вершини ...
