Задачи для самостоятельного решения. Доказательство выходит за пределы данного курса, а потому принимаем теорему без доказательства

Доказательство выходит за пределы данного курса, а потому принимаем теорему без доказательства.

G \Н: v

v₈ v₉ v₁₀

представляет собой результат стягивания графа G по его подграфу H.

Определение 6.5. Растяжение графа G =( V, U ) по ребру e = { v_i, v_j } приводит к графу G’ =( V’, U’ ) в котором V’ = V ∪{ v }, v ∉ V, а U’= ( U \{ { v_i, v_j }})∪{{ v_i, v }, { v, v_j }}. Иными словами, при растяжении графа по ребру в этом графе выбирается конкретное ребро и на этом ребре выбирается новая вершина, не совпадающая с концами исходного ребра, т.е. ребро графа разбивается на два смежных между собой ребра. Обратное действие называется сжатием графа (по паре смежных ребер). Операции растяжения и сжатия графов называются операциями гомеоморфизма.

Определение 6.6. Два графа G и G₁ называются гомеоморфными, если с помощью операций гомеоморфизма из одного графа можно получить граф, изоморфный другому.

Определение 6.7. Говорят, что граф G =( V, U ) правильно укладывается в пространство Eⁿ, если в Eⁿ можно выбрать | V | точек (изображающих вершины графа) и | U | отрезков (дуг) (изображающих ребра графа) так, чтобы эти отрезки (дуги), как ребра графа, пересекались бы только в вершинах им инцидентным.

Теорема 6.1. Любой граф правильно укладывается в пространство Е³.

Доказательство. В пространстве Е³ выберем произвольную прямую l, проведем через нее | U | различных плоскостей и занумеруем их. На прямой l выберем | V | различных точек, изображающих вершины графа и занумеруем их. Занумеруем также ребра исходного графа. Теперь зафиксируем произвольное ребро { v_i, v_j } графа, выберем плоскость, номер которой совпадает с номером этого ребра и проведем в этой плоскости дугу, соединяющую точки (вершины графа) с номерами i и j. Таким образом, различные ребра если и будут пересекаться, то только в точках прямой l в вершинах, которые инцидентны этим ребрам. Следовательно, граф будет правильно уложен в пространство Е³. Теорема доказана.

Определение 6.8. Граф называется плоским или планарным, если он допускает правильную укладку в пространство Е² (правильное изображение на плоскости).

Теорема 6.2 (критерий Понтрягина – Куратовского).

Граф планарен тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного хотя бы одному из графов К₅ или К_3,3, где

К₅ :, а К_3,3 :

Задача 1. Для орграфа, заданного на рисунке:

v₁v₂

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]"> v₃v₄

v₅v₆

1) Найти полустепени захода и исхода, степень каждой из вершин;

2) Имеет ли граф источники и стоки?

3) Имеет ли граф простые циклы? Если да, то указать хотя бы один

из них и определить его длину.

4) Выяснить, является ли граф связным? Если нет, то найти хотя бы

одну его компоненту связности.

5) Нарисуйте граф, ассоциированный с данным орграфом.

6) Какой простой путь в исходном графе имеет максимальную

длину? Какова эта длина?

7) Сколько путей длины 2 существует у исходного графа?

8) Постройте матрицы инцидентности орграфа и ассоциированного

с ним графа.

9) Постройте матрицы смежности орграфа и ассоциированного с

ним графа.

10) Является ли орграф плоским?

Задача 2. Орграф задан своей матрицей инцидентности. Задайте его

геометрически и ответьте на все вопросы предыдущей задачи.

Какую информацию о графе можно получить непосредственно на основании матрицы инцидентности? Найдите матрицу смежности графа, ассоциированного с заданным орграфом.

Задача 3. Орграф задан своей матрицей смежности. Задайте его

геометрически и ответьте на все вопросы задачи 7.1.

Какую информацию о графе можно получить непосредственно на основании матрицы смежности? Найдите матрицу инцидентности исходного орграфа и графа, ассоциированного с заданным орграфом.

Задача 4. Являются ли изоморфными следующие графы?

К_3,3: и

Дата добавления: 2014-12-16