Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Количество росчерков

Из теорем 6 и 7 следует, что для изображения графа, имеющего не более двух нечетных вершин, достаточно одного росчерка. Подсчитаем количество росчерков, необходимых для изображения графа, содержащего более двух вершин нечетной степени.

Теорема 8. Для связного графа, имеющего нечетные вершины, необходимое количество росчерков равно половине количества нечетных вершин.

Доказательство. Предположим, что связный граф G имеет 2п нечетных вершин (по теореме 1 это количество всегда четно). Зафиксируем две нечетные вершины А и В, а остальные нечетные вершины разобьем на пары. В результате получим (п-1) пар. Соединив вершины в этих парах новыми ребрами, получим сверхграф G] исходного графа, который имеет на п-1 ребер больше, чем исходный граф. Так как связный граф G; имеет ровно две нечетные вершины А и В, то он рисуется одним росчерком, причем начало и конец уникурсальной цепи находятся в точках А и В. Если теперь вернуться к графу G, удалив п-1 ребер, то нам придется «разорвать» уникурсальную цепь п-1 раз. Итак, при изображении графа G необходимо оторвать карандаш п-1 раз, т.е. необходимо ровно и росчерков.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы