Особенности применения теории графов при решении задач и в практической деятельности

курсовая работа

5.3 Путь и контур. Длина пути и контура. Длина петли

Последовательность дуг, при которой конец одной дуги является началом другой, называется путём. Если начальная и конечная точки пути совпадают, образуется контур. Длиной пути (или контура) называют число дуг, которые его образуют. Петля - контур единичной длины. Будем также под длиной пути от одной вершины до другой понимать количество рёбер, входящих в соответствующий маршрут. То есть будем применять термин “длина пути” не только к орграфам. Во всех случаях для орграфов и для неориентированных графов дуги и рёбра будем считать столько раз, сколько раз они входят в путь или маршрут.

Связный граф. Граф называется связным, если любая пара вершин соединена маршрутом. Несвязный граф состоит из нескольких отдельно связных графов.

Полный граф. Граф называется полным, если любая пара его вершин соединена ровно одной дугой или ребром.

Рис.7

Число рёбер полного графа с N вершинами. Если полный граф Г имеет N вершин, то он обозначится через КN. Легко видеть, что КN имеет N(N-1) / 2 рёбер.

Простым графом называют граф, который не имеет петель или кратных рёбер. Рис.7. Является ли полный граф простым и однородным графом? Полный граф - это простой граф. Он однозначно задаётся числом своих вершин. Полный граф с N вершинами является однородным степени (N-1), так как из каждой его вершины выходит (N-1) рёбер, ведущих к каждой из остальных (N-1) вершин.

5.4 Плоские и планарные графы

Граф, который можно начертить на плоскости так, чтобы рёбра его пересекались только в его вершинах, называется планарным графом. Его изображение на плоскости без пересечения рёбер назовём плоским графом. Граф, который не является планарным, называется непланарным. Заметим, что в общем случае рёбра графа могут пересекаться между собой, причём точки пересечения не обязательно являются вершинами графа.

Интегральная микросхема состоит из слоёв миниатюрных микросхем, впечатанных в пластину. В такой ситуации крайне важно исключить пересечение проводов в местах, не предназначенных для соединений. Если изобразить места указанных соединений вершинами графа, то возникнет задача построения графа с непересекающимися рёбрами. Важно отметить, что нас интересует возможность построения графа с непересекающимися рёбрами.

Можно также сказать, что граф, изоморфный плоскому графу, называется планарным. Например, все три изоморфных графа (рис.8) Г1 , Г2 , Г3 на следующем рисунке планарные, но только Г2, и Г3 - плоские.

Рис.8

Планарный граф на рис. 9.1 можно изобразить в виде изоморфных плоских графов (рис. 9.2 и рис. 9.3):

Рис.9.1 Рис.9.2 Рис.9.3

Естественно поставить следующий вопрос: всегда ли можно изобразить плоский граф так, чтобы все его рёбра были прямолинейными отрезками? Этот вопрос остаётся открытым.

5.3 Задача о трёх домах и трёх колодцах

На одном участке земли были построены три дома и вырыты три колодца для их обитателей.

Природа страны и её климат таковы, что колодцы часто пересыхают, поэтому важно, чтобы от каждого из домов имелся доступ к каждому из трёх колодцев. Спустя некоторое время обитатели домов А, В, и С (рис.10) серьёзно поссорились друг с другом и решили проложить дорожки к трём колодцам а, b, с так, чтобы по пути к колодцам и обратно им не приходилось встречать друг друга.

Рис.10

А возможно ли это? Является ли соответствующий граф плоским, т.е. можно ли провести дорожки так, чтобы они не пересекались нигде, кроме вершин графа А, В, С и а, b, с? С помощью непосредственной проверки легко убедиться, что всегда можно провести 8 тропинок, которые, кроме указанных точек, других точек пересечения иметь не будут, а девятая тропинка обязательно пересечёт хотя бы одну из них. На рис. 4 показан один из возможных вариантов проведения тропинок. Решим эту задачу посредством рассуждений.

От домиков А и С проведём требуемые тропинки. Полученный граф разделит плоскость на области: X , Y , Z.

Легко заметить, что домик В может находиться в одной из этих областей. Рассмотрим каждый случай в отдельности.

1. Если домик В находится в области Z, как изображено на рисунке, то от него невозможно провести тропинку к b, которая не пересекалась бы ни с одной из уже проведённых тропинок.

2. Если домик В находится в области Y , то от него невозможно провести тропинку к объекту а, которая не пересекалась бы ни с одной из уже проведённых.

3. Если домик В находится в области X, то от него невозможно провести тропинку к объекту c, которая не пересекалась бы ни с одной из уже проведённых.

Итак, получается, что граф, выражающий ситуацию данной задачи, плоским быть не может. А это значит, что задача неразрешима.

Делись добром ;)