Анотація: Визначення графа. Визначення орграфа. Повний граф. Повний орієнтований граф. Двочастковий граф. Ступінь вершини. Можливості підключення графа. Завдання, що призводять до графів
визначення графа
Графом називається пара, де - непорожня скінченна множина елементів, які називаються вершинами. а - кінцеве сімейство невпорядкованих пар елементів з (необов'язково різних), званих ребрами. Вживання слова "сімейство" говорить про те, що допускаються кратні ребра. Будемо називати "безліччю вершин". а - сімейством ребер графа. Про кожному ребрі виду кажуть, що воно поєднує вершини і Кожна петля з'єднує вершину саму з собою.
При зображенні графів на малюнках або схемах відрізки можуть бути прямолінійними або криволінійними; довжини відрізків і розташування точок довільні.
визначення орграфа
Орграф називається пара, де - непорожня скінченна множина елементів, які називаються вершинами, а - кінцеве сімейство упорядкованих пар елементів з, званих дугами (або орієнтованими ребрами). Дуга. у якій вершина є першим елементом, а вершина - другим, називається дугою з в. Зауважимо, що дуги і різні. Хоча графи і орграфа - істотно різні об'єкти, в певних випадках графи можна розглядати як орграф, в яких кожному ребру відповідають дві протилежно орієнтовані дуги.
повний граф
Граф називається повним. якщо кожні дві різні вершини його з'єднані одним і тільки одним ребром. У повному графі кожна його вершина належить одному і тому ж числу ребер. Для завдання повного графа досить знати число його вершин. Повний граф з вершинами зазвичай позначається через.
Граф. який не є повним, можна перетворити в повний з тими ж вершинами, додавши відсутні ребра. Вершини графа і ребра, які додані, теж утворюють граф. Такий граф називають доповненням графа і позначають його.
Доповненням графа називається граф з тими ж вершинами, що і граф, і з тими і тільки тими ребрами, які необхідно додати до графа, щоб вийшов повний граф.
Є граф повним чи ні, це його характеристика в цілому.
Повний орієнтований граф
Повним орієнтованим графом називається граф. кожна пара вершин якого з'єднана в точності одним орієнтованим ребром. Якщо з кожного ребра повного орієнтованого графа зняти напрямок, то утворюється повний граф з неорієнтованими ребрами.
Розглянемо змагання, в якому кожна з команд грає з кожною з інших команд по одному разу. Таке змагання називають круговим турніром або турніром в одне коло.
Якщо кожна зустріч неодмінно повинна закінчуватися виграшем однієї з команд, то коловий турнір називають безкомпромісним. Круговий безкомпромісний турнір проводиться, наприклад, в волейболі та баскетболі.
Кожному турніру відповідає повний орієнтований граф. в якому вершини представляють команди, а кожне орієнтоване ребро виражає відношення "перемогла".