ТИПИ КІНЦЕВИХ ГРАФІВ
Якщо множина вершин графа кінцева, то він називається кінцевим графом. У математику розглядаються і нескінченні графи, але ми займатися ними не будемо, тому що в практичних додатках вони зустрічаються рідко. Кінцевий граф G = (V, Е), що містить р вершин і q ребер, називається (р, q) -графом.
Мал. 3.3. Типи графів: а—псевдограф; б- повний граф (шестикутник); в-двочастковий граф (біграф).
Нехай 
і 
— відповідно безлічі вершин і ребер 
- графа. Кожне ребро 
з'єднує пари вершин 
які є його кінцями (граничними вершинами). Для орієнтованого ребра (дуги) розрізняють початкову вершину, з якої дуга виходить, і кінцеву вершину, у яку дуга заходить. Ребро, граничними вершинами якого є та сама вершина, називається петлею. Ребра з однаковими граничними вершинами є рівнобіжними і називаються кратними. У загальному випадку граф може містити й ізольовані вершини, що не є кінцями ребер і не зв'язані ні між собою, ні з іншими вершинами. Наприклад, для (5,6)-графа на мал. 3.3.,а 
; 
ребра 
і 
рівнобіжні, ребро 
є петлею, а 
— ізольована вершина.
Число ребер, зв'язаних з вершиною 
, (петля враховується двічі), називають ступенем вершини і позначають через 
чи 
. Так, для графа на мал. 9, a 
і т.д. Очевидно, ступінь ізольованої вершини дорівнює нулю 
. Вершина ступеня одиниці називається кінцевою чи висячою вершиною 
. Легко показати, що в будь-якому графі сума ступенів усіх вершин дорівнює подвоєному числу ребер, а число вершин непарного ступеня завжди парне. В орграфі розрізняють позитивні 
і негативні 
ступеня вершин, що рівні відповідно числу що з 
і заходять у , дуг. Наприклад, для вершини 
орграфа (див. мал. 3.2., а) маємо 
і 
. Очевидно, суми позитивних і негативних ступенів усіх вершин орграфа рівні між собою і рівні також числу всіх дуг.
Граф без петель і кратних ребер називають простим чи звичайної. Граф без петель, але з кратними ребрами називають мультиграфом. Найбільш загальний випадок графа, коли допускаються петлі і кратні ребра, називають псевдографом. Так, граф на мал. 3.1,б — це мультиграф, а на мал. 3.3,а — псевдограф. Якщо граф не має ребер 
, то всі його вершини ізольовані 
, і він називається порожнім, чи нуль-графом.
Простий граф, у якому будь-які дві вершини з'єднані ребром, називається повним (на мал. 3.3,б приведений приклад повного графа із шістьма вершинами).
Якщо безліч вершин 
простого графа допускає така розбивка на дві непересічних підмножини 
і 
, що не існує ребер, що з'єднують вершини того самого підмножини, то він називається двочастковим чи біграфом (мал. 3.3,в). Орієнтований граф вважається простим, якщо він не має строго рівнобіжних дуг і петель.
Граф, ступеня усіх вершин якого однакові і рівні 
, називається однорідним (регулярним) 
го ступеня. Повний граф з 
вершинами завжди однорідний ступеня 
, а порожній граф— однорідний ступеня 0. Граф третього ступеня називають кубічним. Він володіє поруч цікавих властивостей і, зокрема, завжди має парне число вершин.