КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Задачи для самостоятельного решения. Доказательство выходит за пределы данного курса, а потому принимаем теорему без доказательства
Доказательство выходит за пределы данного курса, а потому принимаем теорему без доказательства. G \Н: v
v8 v9 v10 представляет собой результат стягивания графа G по его подграфу H. Определение 6.5. Растяжение графа G =( V, U ) по ребру e = { vi, vj } приводит к графу G’ =( V’, U’ ) в котором V’ = V ∪{ v }, v ∉ V, а U’= ( U \{ { vi, vj }})∪{{ vi, v }, { v, vj }}. Иными словами, при растяжении графа по ребру в этом графе выбирается конкретное ребро и на этом ребре выбирается новая вершина, не совпадающая с концами исходного ребра, т.е. ребро графа разбивается на два смежных между собой ребра. Обратное действие называется сжатием графа (по паре смежных ребер). Операции растяжения и сжатия графов называются операциями гомеоморфизма. Определение 6.6. Два графа G и G1 называются гомеоморфными, если с помощью операций гомеоморфизма из одного графа можно получить граф, изоморфный другому. Определение 6.7. Говорят, что граф G =( V, U ) правильно укладывается в пространство En, если в En можно выбрать | V | точек (изображающих вершины графа) и | U | отрезков (дуг) (изображающих ребра графа) так, чтобы эти отрезки (дуги), как ребра графа, пересекались бы только в вершинах им инцидентным. Теорема 6.1. Любой граф правильно укладывается в пространство Е3. Доказательство. В пространстве Е3 выберем произвольную прямую l, проведем через нее | U | различных плоскостей и занумеруем их. На прямой l выберем | V | различных точек, изображающих вершины графа и занумеруем их. Занумеруем также ребра исходного графа. Теперь зафиксируем произвольное ребро { vi, vj } графа, выберем плоскость, номер которой совпадает с номером этого ребра и проведем в этой плоскости дугу, соединяющую точки (вершины графа) с номерами i и j. Таким образом, различные ребра если и будут пересекаться, то только в точках прямой l в вершинах, которые инцидентны этим ребрам. Следовательно, граф будет правильно уложен в пространство Е3. Теорема доказана.
Определение 6.8. Граф называется плоским или планарным, если он допускает правильную укладку в пространство Е2 (правильное изображение на плоскости). Теорема 6.2 (критерий Понтрягина – Куратовского). Граф планарен тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного хотя бы одному из графов К5 или К3,3, где К5 :, а К3,3 :
Задача 1. Для орграфа, заданного на рисунке: v1v2 Y ZF8jj6ZYayA7hkNVvZ4MLJiZIFJpPYDGWfsfQcfcBBN5XP8WOGTnis7GAWiUdfC7qnF/alX2+SfV vdYk+9JVh/yU2Q6cuezP8X+kof5xn+Hff/HqGwAAAP//AwBQSwMEFAAGAAgAAAAhADCWTaHfAAAA CgEAAA8AAABkcnMvZG93bnJldi54bWxMj8FOwzAQRO9I/IO1SNyoUxxVaYhToUocQApqSw8cnXib RMTrKHbb8PcsJ7jNaJ9mZ4rN7AZxwSn0njQsFwkIpMbbnloNx4+XhwxEiIasGTyhhm8MsClvbwqT W3+lPV4OsRUcQiE3GroYx1zK0HToTFj4EYlvJz85E9lOrbSTuXK4G+RjkqykMz3xh86MuO2w+Tqc nYZq9b6t96f204Tdq9+92WoeVKX1/d38/AQi4hz/YPitz9Wh5E61P5MNYtCgsnTNKIuUJzCQqiWL mkmlMpBlIf9PKH8AAAD//wMAUEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAA AAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAA AAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEAZgxnrwQCAAANBAAADgAA AAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEAMJZNod8AAAAKAQAA DwAAAAAAAAAAAAAAAABeBAAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAGoFAAAAAA== " strokecolor="black [3040]"> v3v4
v5v6 1) Найти полустепени захода и исхода, степень каждой из вершин; 2) Имеет ли граф источники и стоки? 3) Имеет ли граф простые циклы? Если да, то указать хотя бы один из них и определить его длину. 4) Выяснить, является ли граф связным? Если нет, то найти хотя бы одну его компоненту связности. 5) Нарисуйте граф, ассоциированный с данным орграфом. 6) Какой простой путь в исходном графе имеет максимальную длину? Какова эта длина? 7) Сколько путей длины 2 существует у исходного графа? 8) Постройте матрицы инцидентности орграфа и ассоциированного с ним графа. 9) Постройте матрицы смежности орграфа и ассоциированного с ним графа. 10) Является ли орграф плоским? Задача 2. Орграф задан своей матрицей инцидентности. Задайте его
геометрически и ответьте на все вопросы предыдущей задачи. Какую информацию о графе можно получить непосредственно на основании матрицы инцидентности? Найдите матрицу смежности графа, ассоциированного с заданным орграфом. Задача 3. Орграф задан своей матрицей смежности. Задайте его геометрически и ответьте на все вопросы задачи 7.1. Какую информацию о графе можно получить непосредственно на основании матрицы смежности? Найдите матрицу инцидентности исходного орграфа и графа, ассоциированного с заданным орграфом. Задача 4. Являются ли изоморфными следующие графы?
К3,3: и
Дата добавления: 2014-12-16; Просмотров: 484; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |