Дискретная математика

125 отношением эквивалентности и поровдает разбиение множества всех фафов на классы изоморфных графов. Тритт осознавал свою кубтиость. ... Он вообще пе задумывался о форме своего тела. А если бы вдруг и задумался, то решил бы, что она прекрасна. Л. Ашмов § 3. Число ребер графа Пусть G - (неориентированный) граф. Число ребер инцидентных вершине v, будем обозначать через deg(v) и называть локальной степенью, или просто степенью вершины v в графе. Для того чтобы найти число ребер, можно сосчитать число ребер в каждой вершине отдельно и сложить все эти числа. При этом каждое ребро будет сосчитано дважды, поэтому полученное число надо разделить пополам. 1 Итак, число ребер графа равно: т = —'Zdegf v,-). В результате доказана первая теорема теории графов (установленная Л. Эйлером). ! Теорема 5.1, Число ребер графа равно половине суммы локальных I степеней его вершин. Из этой теоремы следует, что сумма степеней всех его вершин является числом четным (равным числу 2т). На графе разделяют два типа вершин; нечетные вершины v, степени deg(v) которых нечетные, и четные вершины v*, имеющие четные степени deg(v*)- Теорема 5.2. Число нечетных вершин любого графа четно, Доказательство, Иначе, 'Zdeg(v,) было бы нечетным числом, что не так, В (п.т) графе для любой вершины v, очевидно, выполняется соотношение 0< deg(v)<п-\. Для мультиграфа, очевидно, имеем; й<deg(\>)< т. Минимальная степень вершин графа G обозначается S(G), максимальная - Л(0). Если S(G)=^ Л(0)=>\ то все вершины имеют олинаковую степень, такой Граф G называется регулярньш или однородным степени г, В этом случае говорят о степени графа и пишут deg(G)=r. Очевидно, для регулярных графов = ^ W, я-число вершин. Регулярный граф степени О совсем не имее- ребер. Регулярные графы степени 3 называют кубическими. Так ка