Курсовая работа: Топологическое представление конечных графов

05.06.2019

Содержание
Введение
Известный французский математик Андре Вейль сказал как-то, что за душу каждого математика борются «дьявол абстрактной алгебры и .ангел топологии».
Топология (от греческого место и учение) – раздел математики, имеющий своим назначением выяснение и исследование в рамках математики идея непрерывности выражает кореное свойство пространства и времени и имеет фундаментальное значение для познания.
Предметом топологии является исследование свойств фигур и их взаимного расположения сохраняющихся гомеоморфизмами.
Главной задачей топологии является выделение и изучение топологических свойств или топологических инвариантов - то есть, свойств сохраняющихся при переходе от одной фигуре к другой. К числу важнейших топологических инвариантов относятся связность, компактность, размерность и другие. Кроме того, топология большое внимание уделяет свойствам типа расположения одной фигуры в другой, сохраняющимся при гомеоморфизмах. Проблематика такого рода началась с теоремы Жордана.
Под фигурой топологии понимается любое множество точек, в котором задано отношение близости между точками и некоторыми подмножествами. Такие фигуры называются топологическими пространствами.
Конкретный запас типов топологических пространств формировался под воздействием разных областей математики.
Первые задачи теории графа были связаны с решением математических задач и головоломок-задач о кенигберских мостах, развития которых привело к циклу задач об обходах графов ; задача о перевозках, решение которых привело к созданию эффективных методов решения транспортных задач и другие.
В проблематике теории графов можно выделить направления носящие более геометрический характер. К первым относится, например, задача о построении графа с заданными свойствами. Топологический характер носят, например, задачи связанные с обходами графов, и задачи возникающие при укладке графа на различных поверхностях.
Примером результатов геометрического направления является, например, необходимое и достаточное условие вложение графа в плоскость.
Наряду с проблемами, носящими математический, геометрический характер имеются специфические задачи. Например, изучаются различные свойства связности графа, исследуется строение графа по свойствам связности. При анализе надежности сетей связи, электронных схем коммуникационных сетей возникает задача о нахождении количеств не пересекающих цепей, соединяющих различные вершины графа.
С привлечением методов топологии изучаются вложения графа в различные поверхности. Построены алгоритмы нахождение минимального рода ориентируемой поверхности, на которой можно расположить граф. Для решения задач, связанных с печатным монтажом электронных схем, модельной является задача о разбиение данного графа на минимальное число плоских графов.
Основные понятия
Граф (от греческого γραφω-пишу)- множество V вершин и набор Е у порядочных и непорядочных пар вершин. Обозначается G(V,E). Неупорядоченная пара вершин называется ребром, упорядоченная пара-другой. Граф содержащий только рёбра называется неориентированным. Граф содержащий только дуги,- ориентированным.
Пара вершин можно соединяться двумя или боли ребрами (дугами одного направления),такие ребра называются кратными.
Дуга может начинаться и кончаться в одной и той же вершине, такая дуга называется петлей.
Ребра, имеющая общую вершину называются смежными. Ребра и любая из его двух вершин называется инцидентными.
Два графа G(V,E) и H(W, I) называются изоморфными, если существует взаимно однозначное соответствие между множествами вершин V, W и множествами ребер Е, I, сохраняющие отношение инцидентности.
Подграфом G/ (V/,E/) графа G (V/,E/) называется граф с множеством вершин V/ V и множеством ребер (дуг) Е/Е, каждое из которых инцидентна только вершинами из V/.
Последовательность ребер (0, 1), (1, 2), . . . , (i-1, i) , ( i ,I+1), …, (r-1, r) называется маршрутом, соединяющими вершины 0 и r . маршрут замкнут если 0=r.
Маршрут называется цепью, если все его ребра различны, и простой цепью если все его вершины различны.
Граф называется связным, если любая пара его вершин соединена маршрутом.
С помощью различных операций можно строить граф из более простых, переходить от одного графа к более простому, разбивать граф на более простые. Среди одноместных операций наиболее употребительны удаление и добавление ребра или вершины, стягивание ребра (отождествление пара смежных вершин) подразбиение ребра и другие. Известны двуместные операции: соединение, сложение различные виды умножений графов.
Такие операции используются для анализа и синтеза графа с заданными свойствами.
Гомеоморфные графы.
Одинаковыми графами является гомеоморфные графы-такие графы G1 и G2 для которых существует непрерывное (без разрывов) отображение h : G1  G2 множества G1 на все множество G2 . Такое отражение называется гомеоморфизмом. Из этого определения следует, что два графа гомеоморфные, в частности если, как угодно изгибая и растягивая ребро, но не допуская разрывов и склеиваний, можно один из них наложить на другой: На рисунке 1а показано, как можно окружность превратить в восьмерку; однако это не означает, что окружность и восьмерка гомеоморфные.
Окружность можно превратить и в полуинтервал, но для этого ее нужно разорвать и лишь потом распрямить. Поскольку разрывы не разрешены, такое превращение не будет гомеоморфизмом; к тому же полуинтервал не является графом. А вот контур треугольника и контур квадрата гомеоморфны, и оба они гомеоморфны окружности на рис. 1б.
Заметим что не всегда удается реализовать гомеоморфное отображение h : G1  G2 изгибанием, растяжением и сжатием графов в самом пространстве. Так, пара зацепленных, хотя в пространстве расцепить их, не разрывая, невозможно (рис 2).
Как показывает пример с треугольником и квадратом, при гомеоморфизме вершина не обязана перейти в вершину.
Пример 1. будем представлять себе буквы русского алфавита в виде линий. Буквы Г,Л,М,П,С гомеоморфны между собой. Буквы Е,У,Т,Ч,Ш,Ц,Э также гомеоморфны между собой, но не гомеоморфны указанным ранее буквам. Буква О не гомеоморфна никакой другой букве русского алфавита.
Поучительно сравнить понятие гомеоморфизма и понятие конгруэнтности фигур. В геометрии рассматриваются перемещения. То есть отображения, сохраняющие расстояния между точками. Для фигур которые переводятся одна в другую («совмещаются») с помощью перемещения называются конгруэнтными и рассматриваются как одинаковые. В топологии рассматриваются отображения более общие, чем перемещения, а именно гомеоморфные отображения, которые могут не сохранять расстояний, а сохраняют лишь непрерывность расположения точек в фигурах. Поэтому две гомеоморфные между собой фигуры рассматриваются как одинаковые (с топологической точки зрения).
Простейшие инварианты.
Свойства фигур , которые сохраняются при переходе от фигуры к гомеоморфной ей фигуры называются топологическими свойствами фигур, или топологическими инвариантами (от латинского слова invariant – неизменный).
Чаще всего применяют такие топологические инварианты, которые являются числами, так как с такими инвариантами удобно обращаться. Используются они в основном для решения на первый взгляд безнадежной задачи: доказать что две фигуры А и В не гомеоморфны.
Доказывая, что нечто можно построить (гомеоморфизм h : А  В), достаточно придумать один вариант этого построения. А как доказать что нечто нельзя построить? Для этого нужно перебрать всевозможные варианты построений и проверить что ни один вариант не годится. Но обычно отображений h : А  В бесконечно много, всех не проверить. Как быть?
Здесь и помогают числовые инварианты. Пусть каждой фигуре А рассматриваемого класса приписывается число q(А) причем гомеоморфным фигурам приписываются одно и то же число. Пусть фигуры А и В таковы, что q(А)  q(В). Тогда они не могут быть гомеоморфизм h : А  В!
Удивительная простота этого рассуждения скрывает его глубину и важность.
Пример 2. Буква Ы представляет собой фигуру, состоящую их двух не связанных между собой частей. Большинство остальных букв русского алфавита состоит из одного связного куска (исключение составляют буквы Й, Ё). Число связанных «кусков» из которых состоит фигура (число компонент фигуры) является топологическим инвариантам. Поэтому буква Ы не гомеоморфна, например букве О, букве П,Ц и т.д.
Пример 3. На восьмерке (рис.2а) имеется такая точка Х, что после ее удаления (рис.2б) мы получаем несвязную фигуру (содержащую больше одной компоненты). Точку, обладающую этим свойством, называют разбивающей точкой фигуры. Никакая отличная от Х точка восьмерки не является разбивающей (рис.3в).
Если точка Х фигуры А является разбивающей, она остается таковой при любом гомеоморфизме фигуры А, аналогично- для не разбивающей точки. Поэтому число разбивающих точек - данной фигуры есть ее топологический инвариант, число не разбивающих точек также топологический инвариант.
Пример 4. Пусть А граф и х-его вершина. Число ребер графа А, сходящихся в х, называется индексам вершины х в графе А (при этом петля-ребро с началом и концом в одной и той же вершине х-считается за два ребра, ибо она входит в х двумя своими концами). На рисунке 4 вершины a, b, c, d имеют индексы 1,2,3,4 соответственно. Число вершин индекса n  2, содержащихся в графе топологический инвариант.
Граф называется уникурсальным (или эйлеровым), если его можно нарисовать одним «росчерком», то есть обойти его весь непрерывным движением не проходя одно и то же ребро дважды. Свойство графа быть уникурсальным является, очевидно топологическим инвариантном. Однако этот топологический инвариант не является новым, а выражается через понятие индекса вершины.
С уникурсальными графами связана задача о кенигберских мостах, рассмотренная еще Эйлером. В то время в Кенигсберге было семь мостов через реку Прегель Задача состоит в том, чтобы выяснить, можно ли, прогуливаясь по городу, пройти через каждый мост точно по одному разу. Сопоставим с планом города некоторый граф: вершина Л обозначает левый берег, П - правый берег, А и Б- острова, а ребра графа соответствуют мостам . В этом графе все четыре вершины имеют нечетный индекс. Следовательно граф не уникурсален и поэтому требуемого маршрута не существует.
Связный граф.
Всякий граф можно «построить» добавляя одно ребро за другим (при этом нужно будет отличать и вершины графа). Нумерация ребер графа на рис.5 выбрана так, что при вычерчивании все время получаются связные графы. Если бы, однако, мы занумеровали ребра в обратном порядке, то при вычерчивании у нас сначала получался бы несвязный граф. Оказывается, во всяком связном графе существует такая нумерация ребер, что при вычеркивании графа в соответствии с этой нумерацией все время получаются связные графы. Это утверждение можно назвать «теоремой о вычерчивании связных графов».
Дерево.
Контуром в графе называется замкнутая цепочка ребер, объединение которых представляет собой линию гомеоморфную окружности . Связный граф, не содержащий ни одного контура, называется деревом . Докажем, что в любом дереве число вершин и число ребер Р связны соотношением:
В – Р = 1. (1)
Для доказательства проведем индукцию по числу ребер Р. При Р=1 (дерево состоит только из одного ребра и имеет две вершины) соотношение (1) справедливо. Предположим что для любого дерева, имеющего n ребер, соотношение (1) уже доказано, и пусть G- дерево, имеющее n+1 ребер. Так как граф G- связный, его можно получить из некоторого связного графа G/ добавлением одного ребра r. Граф G/ содержит n ребер и тоже является деревом. По предположению индукции соотношение (1) для графа G/ справедливо, и потому в нем имеется n+1 вершин.
Заметим теперь, что только один конец добавляемого ребра r является вершиной графа G/ (иначе при добавлении ребра r в графе G появился бы контур). Следовательно при добавлении ребра r в графе G появляется одно новое ребро и одна новая вершина. Иначе говоря, в графе G имеется n+2 вершин и n+1 ребер, и потому соотношение (1) для него справедливо. Проведенная индукция доказывает равенство (1) для любого дерева.
Разность В – Р называется Эйлеровой характеристикой графа G и обозначается через Х(G). Таким образом, равенство (1) означает, что Эйлерова характеристика любого дерева равна 1.
Максимальное дерево и системы токов.
Пусть теперь G- связный граф, не являющийся деревом. Тогда в G имеется контур; пусть r1 – какое-либо ребро, входящее в этот контур . Удалив из G ребро r1 , мы получим связный граф G/ (поскольку концы выброшенного ребра r1 соединены в G/ простой цепочкой – оставшейся частью контура) причем вершины у графа G/ -те же что и у G.
Если G/ не является деревом, то есть G/ так же имеется контур , то мы можем взять произвольное ребро r2 этого контура и выбросив его получим связный граф G //и т.д. Так как число ребер конечно, этот процесс должен на каком-то шаге остановиться; иначе говоря, после выбрасывания какого-то ребра rк мы получим связный граф G* содержащий все вершины графа G и уже не имеющий контуров, то есть являющийся деревом. Граф G* называется максимальным деревом графа G, а ребра r1, r2, …, rк которые пришлось выбросить из G,чтобы получить максимальное дерево G*, называются перемычками.
Если В- число вершин графа G, то максимальное дерево G* тоже имеет В вершин.
Согласно (1), граф имеет В-1 ребер, и потому число ребер графа G равно В-1+R (чтобы из G* получить G надо «возвратить» R выброшенных ребер-перемычек). Следовательно:
Х(G)= В-(В-1+R)= 1- R (2)
Так как R  1, получаем Х(G) ≤ 0. Таким образом, учитывая (1), мы видим, что для любого связного графа G справедливо соотношение:
Х(G) ≤ 1.
Причем равенство достигается в том и только в том случая, когда G- дерево.
Далее, согласно (2), число перемычек равно:
R=1- Х(G).
Плоские и планарные графы.
Плоским графом называются граф вершины которого являются точками плоскости, а ребра – непрерывными плоскими линиями без самопересечений, соединяющие соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Примеры плоских графов даны на рис.6
Любой граф изоморфный плоскому называется планарным. Граф К4 (рис.7) является планарным так как он изоморфен графам на рис.6 б,в.
Из этого следует следующие утверждения;
1) Всякий подграф планарного графа планарен;
2) Граф планарен только тогда, когда каждая его связная компонента – планарный граф.
Говорят, что планарные графы укладываются на плоскости то есть имеют плоскую укладку. Но графы укладываются не только на плоскости, но и на других поверхностях и в пространстве.
Прежде всего введем понятие жордановой кривой или жордановая дуга. Жордановая дуга – это непрерывная устремляемая линия не имеющая самопересечений.
Граф G укладывается в пространство L, если существует такое отображение вершин и ребер графа G соответственно в точки жордановы кривые этого пространства, что различным вершинам соответствуют различные точки, а кривые соответствующие ребрам, пересекаются только в инцидентных этим ребрам вершинах.
Изображенный таким образом граф называется укладкой графа G в пространство L.
Теорема 1.1. Каждый граф укладывается в трехмерное пространство Е3.
Доказательство: Все вершины графа G помещаем в различные точки оси ОХ. Из пучка плоскостей выберем
|Е G | различные плоскостей. Далее, каждое ребро uv EG изображаем в соответствующей плоскости полуокружностью, проходящей через вершины u и v. В результате получаем укладку графа G в Е3 , так как все ребра лежат в разных плоскостях и потому не пересекаются во внутренних точках.
Теорема 1.2. Граф укладывается на сфере тогда и только тогда, когда он планарен. Для доказательство этой теоремы достаточно рассмотреть стереографическую проекцию (рис.8). пусть граф G уложен на сфере. Проведем плоскость Q, касательную к сфере, так чтобы северный полюс N (точка, диаметрально противоположная точке касания) не лежа я на ребре и не совпадая с вершиной графа G. Рассмотрим граф G/ , полученный стереографической проекций графа G из точки N на плоскость Q. Поскольку существует биективное соответствие между точками сферы, отличными от граф G/ плоский и изоморфен графу G. Следовательно, G – планарный граф.
Следующая классическая головоломка наводит на мысль, что существует не только планарные графы.
Задача о трех домах и трех колодцах.
Имеются три дома 1,2,3 и три колодца 4,5,6 (рис.9). каждый хозяин пользуется любым из трех колодцев. В некоторый момент обитатели решили приложить дорожки до колодцев так, чтобы дорожки не пересекались.
Возникает вопрос: Можно ли построить плоскую укладку этого графа К3,3? Все попытки нарисовать девять не пересекающихся дорожек соединяющих дома с колодцами заканчиваются неудачей. При этом можно нарисовать восемь непересекающихся дорожек, но девятая обязательно хотя бы одну из этих восьми. Далее будет доказано что граф К3,3 не укладывается на плоскости, то есть не является планарным.
Многоугольник замкнутая ломанная линия, которая получается, если взять n любых точек А1, А2,…., А n и соединить прямолинейным отрезком каждую из них с последующей, а последнюю – с первой.
Многогранник в трехмерном пространстве – совокупность конечного числа плоских многоугольников, такая что: 1) каждая сторона любого из
.....