елі, зображені на рис. 5.1 а, б, в, з подивимось Теорії графів однакові.
Малюнок 5.1 - Графи
Визначення. Напрямлені ребра назівають орієнтованімі ребрами або дугами, перша по черзі вершина назівається качаном дуги, а друга - ее кінцем. Граф, что містіть напрямлені ребра, назівається орієнтованім графом або Орграф (рис. 5.2, а), а граф, что НЕ містіть напрямленості ребер - неорієнтованім або н-графом (рис. 5.2, б).
Малюнок 5.2 - орієнтований та неорієнтованій граф
Визначення. Ребро, что з'єднує Деяк вершину саму Із собою, назівається петлею (рис. 5.3, а).
Визначення. Ребра, інцідентні до однієї и тієї ж вершини, назіваються кратним (рис. 5.3, б). Граф, что містіть кратні ребра, назівається мультиграфом, а граф, что містіть кратні ребра и петлі - псевдографом.
Визначення. Граф назівається кінцевім, если множини его вершин и ребер звічайна.
множини ребер графа может буті порожніх (рис. 5.3, в). Такий граф назівається порожнім або пустимо.
Малюнок 5.3 - Віді графів
Визначення. Граф без петель и кратних ребер назівається ПОВНЕ, если Кожна пара его вершин з'єднана ребром. Повний граф з вершинами позначається.
Приклад. На рис. 5.4 зображені повні графи,,, и відповідно:
Малюнок 5.4 - Повні графи
Визначення. ДОПОВНЕННЯ графа назівається граф, что має ті ж вершини, что и граф и только ті ребра, Які необходимо Додати до графа, щоб ВІН ставши ПОВНЕ.
Приклад. ДОПОВНЕННЯ графа, збережений на рис. 5.5, а є граф, збережений на рис. 5.5, б. Для порівняння, повний граф збережений на рис. 5.5, в.
Малюнок 5.5 - Віді графів
Визначення. Ступінь вершини назівається Кількість ребер, інцідентніх Цій вершіні. Вершина степеня 0 назівається ізольованою. У графі з петлями петля дает внесок в 2 одиниці у степінь вершини.
Теорема 1. Сума ступенів вершин графа всегда парна:, де - Кількість ребер графа.
Доведення: Тому що Кожне ребро графа має дві кінці, степінь шкірного кінця збільшується на 1 за рахунок одного ребра. Тобто у торбу ступенів всех вершин Кожне ребро вносити 2 одиниці. Отже, сума ступенів вершин винна у дві разї перевіщуваті число ребер, тобто буті хлопця.
Теорема 2. У будь-якому графі Кількість вершин непарного степеня парна.
Доведення: Доведемо від оберненого. Припустиме, є непарний число вершин непарного степеня. Сума вершин парного степеня - парна. Сума степенів всех вершин графа є сума вершин непарного и парного степенів. Така сума всегда є число непарний. Тобто сума степенів всех вершин графа буде непарна. Це суперечіть умові теореми 6.1. Прийшли до протіріччя. Отже, Кількість вершин непарного степеня в будь-якому графі парна.
Справедлівість теорем 1 і 2 можна проілюструваті на Наступний прікладі.
Приклад. Візначіті степені вершин графа, збережений на Наступний малюнку.
розв язання:; ; ; ; ;.
.
У Розглянуто графі дев ять ребер, а вершин непарного степеня две:;.
Визначення. Для орієнтованого графа визначаються две степені вершин: - Кількість ребер, что Виходять Із вершини і - Кількість ребер, что входять у вершину. Петля дает внесок по одиниці в обідві степені.
У орграфі суми степенів всех вершин и Рівні между собою и дорівнюють кількості ребер цього графа:
.
Приклад. Візначіті степені вершин орграфа, збережений на Наступний малюнку.
розв язання:
,; ; ; ;
,; ; ; ;
.
Визначення. Граф назівається підграфом графа, если Кожна вершина и Кожне ребро графа є відповідно вершиною и ребром графа.
Визначення. Граф назівається остов (каркас) графа, если містіть всі его вершини. За визначенням ВІН такоже є підграфом графа.
Приклад. На рис. 5.6 (а, б, в) зображені підграфі графа, збережений на рис. 5.6, г. Причем підграф (рис. 5.6, б) є его каркас.
Малюнок 5.6 - Підграфі графа
Один и тій же граф можна зображуваті по-різному. Різнім чином можна розташовуваті вершини на площіні и ребра можна зображуваті НЕ только відрізкамі прямих (різної довжина) но и дугами. Тому порівнюючі граф...
