Связность графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
что невозможно.
С понятием остовного леса Т графа G тесно связано понятие фундаментальной системы циклов, ассоциированной с Т. Оно определяется следующим образом: если добавить к Т любое не содержащееся в нем ребро графа G , то по предложению (vi) теоремы 9А получим единственный цикл; множество всех циклов, получаемых таким способом (т. е. путем добавления по отдельности каждого ребра из G, не содержащегося в Т), называется фундаментальной системой циклов, ассоциированной с T. В том случае, когда нас не интересует, какой остовный лес рассматривается, фундаментальная система циклов графа G. Ясно, что циклы данной фундаментальной системы должны быть различными и что их число должно равняться циклическому рангу графа G. На Рис. 4 показана фундаментальная система циклов графа, изображенного на Рис. 2, ассоциированная с остовным деревом, изображенным на Рис. 3.
Рис. 4
Надеяться, что удастся определить фундаментальную систему разрезов графа С, ассоциированную с данным остовным лесом Т. Покажу, что это действительно можно сделать. По предложению (iv) теоремы 9А удаление любого ребра из Т разбивает множество вершин дерева Т на два непересекающихся подмножества V1 и V2. Множество всех, ребер графа G, каждое из которых соединяет вершину из V1 с вершиной из V2 является разрезом графа G. Множество всех разрезов, полученных таким способом (т. е. удалением по отдельности каждого ребра из Т), называется фундаментальной системой разрезов, ассоциированной с Т. Ясно, что разрезы данной фундаментальной системы должны быть различными и что их число должно равняться коциклическому рангу графа С. Фундаментальной системой разрезов графа, изображенного на Рис. 2, ассоциированной с остовным деревом, изображенным на Рис. 3, является такая система: {е1, е5}, {е2, е5, е7, е8}, {е3, е6, е7, е8} и {е4, е6, е8}.
ПРАКТИЧЕСКАЯ ЧАСТЬ
1) Можно ли ходом шахматного коня обойти шахматную доску размером
Х8 так, чтобы каждый ход встречался ровно один раз (при этом мы считаем, что ход встречался, если конь переместился с одной клетки на другую любым из двух возможных способов)? Тот же вопрос для короля и ладьи. Как изменятся ответы для шахматной доски размером 7X7? Изложите свои ответы в терминах теории графов.
Ответ: Для доски 8х8:Что бы каждый ход встречался ровно один раз,должно выполняться условие: конь должен зайти на клетку и сойти с неё т.е перейдя к терминам теории графов ,получим :клетка-вершина графа ,каждая вершина имеет степень равную 2 (есть 2 ребра вход и выход).Значит степень каждой вершины будет чётной => согласно теореме этот граф будет гамильтоновым, а значит существует гамильтонова цепь-путь обхода шахматной доски. Данное утверждение справедливо не только для коня, но для ладьи и короля. Эти соображения не изменяются и для шахматной доски размером 7х7.
2) В графе Петерсена найдите (i) маршрут длины 4; (ii) циклы длины 5, 6, 8 и 9; (iii) разрезы, содержащие 3, 4 и 5 ребер
Ответ:
) a>b>c>h>l(маршрут длины 4)
) а)f>h>l>g>k>f (цикл длины 5)
В) a>b>c>d>k>f>a (6)) h>l>g>k>f>a>b>c>h (8)) d>e>l>g>b>c>h>f>k>d (9)
3) a) {1,2,3} -(разрез,содержащий 3 ребра)
b) {1,2,3,7} (4)
c) {4,5,6,7,8} (5)
3) Докажите, что ребро связного графа является мостом и в том и только в том случае, когда оно не содержится ни в одном из циклов
Ответ: Ребро {a,b} является мостом в том и только в том случае ,если оно не принадлежит ни одному циклу.
Прямая теорема: Если ребро{a,b} не принадлежит ни одному циклу ,при его удалении не остаётся пути, связывающего а и в то есть {a,b} является мостом.
Обратная теорема: Если ребро {a,b} -мост, то {a,b} не принадлежит ни одному циклу. Если бы ребро {a,b} принадлежало циклу, то пути удалении ребра {a,b} остался бы второй путь, связывающий а и в , то есть ребро {a,b} не было бы мостом следовательно {a,b} не принадлежит циклу.
4) В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде?
Ответ:
Решение этой задачи достигается построением графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.
Иными словами, суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа.
Любая географическая карта является многоугольным графом, в котором страны будут гранями, границы - ребрами, а окружающий страны Мировой океан - бесконечной гранью.Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют "правильно" раскрашенной.
Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому вопросу уделяется большое внимание в популярной литературе, и здесь мы не будем останавливаться на его рассмотрении.
Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от бумаги являются одним из математических развлечений. При решении подобных задач необходимо помнить следующее положение.
Для того, чтобы на графе имелась цепь, соединяющая АА и ВВ, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы ?/p>