Числові характеристики графа

Означення 2.1.10. Напівстепенем виходу вершини називають кількість вихідних з неї дуг.

Означення 2.1.11. Напівстепенем входу вершини називають кількість вхідних до неї дуг.

Означення 2.1.12. Степенем (валентністю) вершини називають суму її вхідних та вихідних дуг.

.

Вершину, степінь якої дорівнює 0, називають ізольованою. Вершину, степінь якої дорівнює 1, називають висячою.

Граф, всі вершини якого мають однаковий степінь, називають регулярним або однорідним.

Лема про рукостискання. Сума степенів всіх вершин графа є парним числом.

Наслідок. У довільному графі кількість вершин непарного степеня – число парне.

Теорема 2.1.1. Максимальна кількість ребер у плоскому графі обчислюється за формулою .

Теорема 2.1.2. Кількість ребер у повному графі обчислюється за формулою .

Теорема 2.1.3. Кількість ребер у регулярному плоскому графі обчислюється за формулою , де – показник регулярності графа (степінь всіх вершин).

Теорема 2.1.4. Найбільша кількість ребер у графі, який не має трикутних граней, обчислюється за формулою .

Теорема 2.1.5. Максимальна кількість ребер у повному дводольному графі обчислюється за формулою , де .

Теорема 2.1.6. Стала залежність між кількістю вершин, ребер і граней плоского графа визначається за формулою Ейлера: , де – кількість вершин, – кількість ребер, а – кількість граней графа.