Сформулируем некоторые закономерности, присущие определенным графам.
Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Доказательство:
Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро, что и требовалось доказать.
Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа.
Доказательство:
Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R — число ребер графа), т. к. каждое ребро было подсчитано дважды, что и требовалось доказать.
ТЕОРЕМА. Число нечетных вершин любого графа четно.
Доказательство:
Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2;...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как K1 + 2К2 + ЗК3 +...+ nКn. С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство K1 + 2К2 + ЗК3 +... + nКn = 2R. (1) Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 +...):K1 + 2К2 + ЗК3 +К4 + 5К5 +... + nК = 2R, (К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 +...)=2R Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число. Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2
|
|
|
Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.
Эйлеровы графы.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6)
Такими графы названы в честь учёного Леонарда Эйлера.
Закономерность 3 (вытекает из рассмотренной намитеоремы). Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 5. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
|
|
|
Дата добавления: 2016-01-06; просмотров: 15; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!