кання двох людей, то отрімаємо, что при будь-якому чіслі рукостіскань загальна кількість потіснутіх рук буде хлопцем.
Наслідок 1.2.1 У будь-якому графі число вершин непарного степеня хлопця. Дійсно, Якби це Було не так, то сума степенів всех вершин графа не могла б буті парних числах, что суперечіть лемі про рукостіскання. p> Графи ЗРУЧНИЙ зображуваті на площіні або в просторі у вігляді діаграм, Які складаються з точок и відрізків, что з'єднують деякі з ціх точок. При цьом точки ототожнюються з вершинами графа, а відрізкі - з йо ребрами. p> Граф может містіті декілька Однаково ребер. Такі ребра назіваються кратних . Граф Який містіть кратні ребра назівається мультиграфом .
Означення 1.2.2 Підграфом графа G = (V, Е) назівається граф G '= (V', Е '), у якому Е 'з Е і V з V.
Если кінці ребра співпадають то ВІН назівається за сітку .
Граф, Який містіть кратні ребра и петлі назівається псевдографом .
В
Рис. 1.2.3 Зображено а) псевдографом, б) мультограф, в) граф
.3 Різновіді графів
Розглянемо деякі різновіді графів, Які часто зустрічаються.
В
Рис. 1.3.1 Граф До 4 Рис. 1.3.2 Граф К 5
повні графи
Означення 1.3.1.1 Граф, будь-які Дві вершини Якого суміжні, назівається ПОВНЕ графом. Отже, ЯКЩО G = (V, Е) - повний граф, то Е = V 2 . Повний граф з n вершинами позначаємо К n Графи К 4 і К 5 зображені на рис. 1.3.1 и 1.3.2 відповідно.
Регулярні графи
Більш загально, чем повні, є регулярні графи.
Означення 1.3.2.1 Граф назівається регулярним або одноріднім, ЯКЩО ВСІ йо вершини мают один и тієї ж степінь . Якшо степінь кожної вершини дорівнює k, то граф назівається регулярним графом степеня k. Отже, повний граф n-го порядку є регулярним графом степеня n-1. Регулярні графи степеня 3 назівають такоже кубічнімі, або трівалентнімі графами (ці графи віклікають особливий Інтерес у зв'язку Із задачею розфарбування графів). Відомим прикладом кубічного графа є граф Петерсена, Який показано на рис. 1.3.2.1.
В
Рис. 1.3.2.1 Граф Петерсена
Платонові графі
Означення 1.3.3.1. Пла...
