і можливі ребра, називаються неповними графами (ріс.1.3.3).
Графи, в яких побудовані всі можливі ребра, називаються повними графами (ріс.1.3.4).
ріс.1.3.2 ріс.1.3.3
ріс.1.3.4
Граф, кожна вершина якого з'єднана з ребром будь-який інший вершини, називається повним. Зауважимо, що якщо повний граф має n вершин, то кількість ребер дорівнюватиме n (n - 1)/2. Дійсно, кількість ребер у повному графі з n вершинами визначається як число невпорядкованих пар, складених з усіх n точок-ребер графа, тобто як число сполучень із n елементів по 2: граф, який не є повним, можна доповнити до повного з тими ж вершинами, додавши бракуючі ребра. Так, наприклад, на малюнку 1.3.3 зображений неповний граф з п'ятьма вершинами. На малюнку 1.3.4 ребра перетворюють граф в повний граф зображені іншим кольором, сукупність вершин графа з цими ребрами називається доповненням графа.
а) Ступені вершин і підрахунок числа ребер.
Кількість ребер, що виходять з вершини графа, називається ступенем вершини. Вершина графа, що має непарну ступінь, називається непарною, а парну ступінь - парною. Якщо ступені всіх вершин графа рівні, то граф називається однорідним. Таким чином, будь-який повний граф - однорідний.
ріс.1.3.5
На малюнку 1.3.5 зображений граф з п'ятьма вершинами. Ступінь вершини А позначимо ст.А. На малюнку: ст.А=1, ст.Б=2, ст.в=3, ст.Г=2, ст.Д=0.
Сформулюємо деякі закономірності, притаманні певним графам.
Закономірність 1. Ступені вершин повного графа однакові, і кожна з них на 1 менше числа вершин цього графа.
Доказ: ця закономірність очевидна вже після розгляду повного графа. Кожна вершина з'єднана ребром з кожною вершиною, крім самої себе, т. Е. З кожної вершини графа, що має n вершин, виходить n - 1 ребро, що потрібно було довести.
Закономірність 2. Сума ступенів вершин графа число парне, рівне подвоєному числу ребер графа. Ця закономірність справедлива не тільки для повного, а й для будь графа.
Доказ: дійсно, кожне ребро графа пов'язує дві вершини. Значить, якщо будемо складати число ступенів усіх вершин графа, то отримаємо подвоєне число ребер 2R (R - число ребер графа), т. К. Кожне ребро було підраховано двічі, що потрібно було довести.
б) Поняття ейлерови графи.
Спробуємо граф, зображений на ріс.1.3.6, обвести одним розчерком, тобто, не відриваючи олівця від аркуша паперу і не проходячи по одній і тій же частині лінії більше одного разу. Фігура ця, така проста на вигляд, виявляється, має цікаву особливість. Якщо ми почнемо рух з вершини В, то у нас це обов'язково вийде. А що буде, якщо ми почнемо рух з Верин А? Легко переконатися, що обвести лінію в цьому випадку нам не вдається: у нас завжди буде залишатися не пройдені ребра, дістатися до яких вже неможливо.
ріс.1.3.6 Рис.1.3.7
На рис. 1.3.7 зображено граф, який ви, напевно, вмієте малювати одним розчерком. Це зірка. Виявляється, хоча вона і виглядає значно складнішою, ніж попередній граф, обвести її можна, почавши з будь-якої вершини.
Графи, накреслені на ріс.1.3.8 (а, б) і також можна накреслити одним розчерком пера.
рис. 1.3.8а рис. 1.3.8б
Тепер спробуємо вичертити одним розчерком граф, зображений на ріс.1.3.9. Вам це зробити не вдалося! Чому? Ви не можете знайти потрібну вершину? Ні! Справа не в цьому. Цей граф взагалі не можна викреслити одним розчерком пера.
ріс.1.3.9
Проведемо міркування, які переконають нас у цьому. Розглянемо вузол А, з нього виходять три вершини. Почнемо викреслювати граф з цієї вершини. Щоб пройти по кожному з цих ребер, повинні вийти з вершини А по одному з них, в якій - то момент обов'язково повернутися в нього по другому і вийти по третьому. А ось знову увійти вже не зможемо! Значить, якщо ми почнемо викреслювання з вершини А, то закінчити в ньому не зможемо.
Припустимо тепер, що вершина А не є початком. Тоді в процесі викреслювання ми повинні увійти до нього по одному з ребер, вийти з нього по - іншому і знову повернутися по третьому. А так як вийти з нього ми не зможемо, то вершина А в цьому випадку повинен бути кінцем. Але про через три інші вершини нашого графа можна сказати те ж саме. Але ж і початковою вершиною викреслювання може бути тільки одна вершина, і кінцевою вершиною також може бути тільки одна вершина! А значить, викреслювати цей граф одним розчерком неможливо.
Граф, який можна намалювати, не відрив...
