Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
3.1. Основные понятия и определения Теория графов применяется при анализе функционирования сложных систем, таких как сети железных дорог, телефонных или компьютерных сетей, ирригационных систем. Эта теория традиционно является эффективным аппаратом формализации задач экономической и планово – производственной практики, применяется в автоматизации управления производством, в календарном и сетевом планировании. Основным понятием теории является граф. Пусть S - непустое множество, 2 V - множество всех его двухэлементных подмножеств, 2 V U Тогда пара U S, называется неориентированным графом.Элементы множества S называются вершинами графа, а элементы множества U - ребрами. Итак, U S G , граф - это конечное множество вершин S и множество ребер U Вершины графа обозначают по-разному: или большими буквами, или малыми с индексами; для ребер наиболее употребительное обозначение - u с индексом, например, ,..., , 2 1 n u u u Взаимное расположение, форма и длина ребер значения не имеют. Важно лишь то, что они соединяют две данные вершины множества S . Если в паре вершин j i x x и указано направление связи, т. е. какая из вершин является первой, то соединяющий их отрезок k u называется дугой, а вершины, определяющие дугу k u , называют концевыми вершинами. Если концевые вершины совпадают, то дугу называют петлей. В графе G могут существовать дуги (ребра) с одинаковыми концевыми вершинами. Такие дуги называются параллельными. Если в графе U S G , все элементы множества U изображаются дугами, то граф называется ориентированным или орграфом, если ребрами, то неориентированным. Два ребра называются смежными, если они имеют общий конец. Вершина 1 x и ребро 1 u называются инцидентными, если 1 x является концом ребра 1 u и не инцидентными в противном случае. Таким образом, смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами. 51 Число вершин графа называется его порядком. Степенью i x P вершины i x называется число дуг (ребер) графа G , инцидентных данной вершине. Вершина степени нуль называется изолированной, а если степень равна единице, то такая вершина называется висячей. Граф G называется простым, если он не содержит петель и параллельных дуг. Простой граф, в котором каждая пара вершин смежна, называется полным. Граф, содержащий хотя бы две параллельные дуги (ребра), называется мультиграфом. Граф, содержащий петли, называется псевдографом. Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из p и q вершин, обозначается символом q p K , Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. На рисунке 3.1 изображены полные графы порядка 1, 2, 3 и 4. Они обозначаются n K . Число ребер в полном графе 2 n C . На рис. 3.4 изо- бражены двудольные графы 4 , 1 K и 3 , 3 K Два графа G и 1 G называются изоморф- ными, если между множеством их вершин Рис 3.1. существует такое взаимно однозначное соответствие, при котором в одном из графов ребрами соединены вершины в том и только в том случае, если в другом графе ребрами соединены те же вершины. Для орграфов ориентация дуг должна быть также одинаковой. Очевидно, что отношение изоморфизма графов является эквивалентностью, т. е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Способов задания графов - великое множество. Самый простой способ – задание множеств S и U . Граф также может быть задан просто рисунком. В силу изоморфизма один и тот же граф может быть изображен разными рисунками. Например, слева на рисунке 3.2 1 x 3 x 4 x 2 x изображение одного и того же графа, так как в обоих случаях содержится одна и та же информация о вершинах и дугах графа и их взаимном расположении. В некото- 1 x рых случаях все же приходиться разли- чать изоморфные графы, тогда полезно 4 x 2 x 3 x понятие помеченный граф. Рис. 3.2. Граф n G порядка n называется помеченным, если его вершинам присвоены некоторые метки, например, 1, 2, 3… Пусть 3 n , тогда, например, на рисунке 3.3 изображены три разных графа. Строго говоря, абстра- 1 2 3 ктный или непомеченный граф – это класс изоморфных графов. Число n g непоме- ченных графов порядка n определяется 2 3 1 3 1 2 очень сложно. Известна формула Пойа Рис. 3.3. Дьердь Пойа (1887 – 1985) – американский математик. 52 ! 2 2 n g n C n , (3.1.1) дающая лишь асимптотику числа n g , то есть , 1 lim n f n g n где ! 2 , 2 n n f g n g n C n Граф называется плоским (пла- нарным), если он может быть изобра- жен на плоскости так, что все пересече- ния ребер являются его вершинами. 4 , 1 K 3 , 3 K Для произвольного графа U S G , Рис. 3.4. следующим образом определяется до- полнительный граф (дополнение) U S G , . В этом графе G вершин столько же, сколько в графе G , причем любые две несовпадающие вершины смежны в G тогда и только тогда, когда они не смежны в G (см. рис. 3.5). Граф, изоморфный своему дополнению, называется самодополнительным. Пусть U S G , Граф / / / ,U S G называется подграфом графа G , если S S / и U U / U S G , U S G , Рис. 3.5. 3.2. Операции над графами Определим операции, позволяющие из имеющихся графов получать другие графы с большим или меньшим числом элементов. 1) Операция объединения графов. Граф U S G , называется объединением (или наложением) графов 1 1 1 ,U S G и 2 2 2 ,U S G , если 2 1 S S S и 2 1 U U U Объединение 2 1 G G G называется дизъюнктным, если 2 1 S S 2) Произведение графов. Пусть даны графы 1 1 1 ,U S G и 2 2 2 ,U S G . Граф U S G , называется произведением 2 1 G G графов 1 G и 2 G , причем 2 1 S S S - декартово произведение множеств вершин исходных графов, а множество ребер получается следующим образом: вершины 2 1 , x x и 2 1 , y y смежны в графе G тогда и только тогда, когда 1 x 1 1 , y x 2 1 , y x 3 1 , y x или 1 1 y x , а 2 x и 2 y смежны в 2 G , 1 y 2 y 3 y 1 2 , y x 2 2 , y x 3 2 , y x или 2 2 y x , а 1 x и 1 y смежны в 1 G 2 x G (см. рис. 3.6). С помощью операции 1 G 2 G произведения вводятся n -мерные 3 x 1 3 , y x 2 3 , y x 3 3 , y x кубы – один из классов графов. Рис. 3.6. n -мерный куб n Q вводится рекур- рентно: 1 , , 1 2 2 1 n Q K Q K Q n n . (3.2.1) Таким образом, n Q - граф порядка n 2 , вершины которого можно представить векторами длины n , причем такими, что векторы, смежные одной вершине, будут различаться ровно в одной координате. На рисунке 3.7 представлены кубы 2 Q и 3 Q . Видно, что каждая вершина n -мерного куба инцидентна n ребрам, следовательно, число ребер n - мерного куба равно 1 2 n n 53 3) Слияние (отождествление) вершин. Пусть 1 x и 2 x - две произвольные вершины (1,0,1) (1,1,1) 2 x (0,1) (1,1) (0,0,1) (0,1,1) G 1 G (0,0) (1,0) (0,0,0) (0,1,0) 1 x 1 y (1,0,0) (1,1,0) Рис. 3.8. Рис. 3.7. графа G , а 2 1 1 \ \ x x G G . К графу 1 G присоединим новую вершину 1 y , соединив ее ребром с каждой из вершин, входящих в объединение окружений вершин 1 x и 2 x в графе G . Построенный граф 1 G получен из G отождествлением вершин 1 x и 2 x (см. рис. 3.8). Операция стягивания ребра означает отождествление двух смежных вершин. Граф G называется стягиваемым к графу 1 G , если 1 G получается из G в результате некоторой последовательности стягиваний ребер. 4) Расщепление вершин. Пусть 1 x - одна из вершин графа G . Разобьем ее окружение на две части 1 N и 2 N ; удалим вершину 1 x вместе с инцидентными ей ребрами; добавим но- 3 x вые вершины 2 x и 3 x , соединяющее их ребро 1 x 2 x 3 2 , x x ; вершину 2 x соединим с каждой вершиной 2 N из множества 1 N , а вершину 3 x с каждой верши- 1 N ной из множества 2 N . В результате получим граф G . Этот граф построен из исходного графа G Рис. 3.9. расщеплением вершины 1 x (см. рис. 3.9). 3.3. Маршруты, цепи, циклы Чередующая последовательность 1 2 2 1 1 , , ,..., , , , k k k x u x u x u x вершин и ребер графа, такая что k i x x u i i i , 1 , 1 , называется маршрутом, соединяющим вершины 1 1 и k x x Очевидно, что маршрут можно задать последовательностью его вершин 1 2 1 ,..., , k x x x или последовательностью ребер k u u u ,..., , 2 1 . Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Маршрут называется циклическим, если 1 1 k x x . Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется длиной маршрута. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа. Длина всякого цикла не менее трех в графе без петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом. Важным понятием теории графов является связность. Граф называется связным, ес- 2 x 4 x 1 x ли любые две его несовпадающие вершины 2 x соединены маршрутом. Для орграфа сущес- 1 x твует еще понятие сильной связности. Для связный граф этого определим понятие пути. Путь – это сильно (нет пути из 2 x в 3 x ) ориентированный маршрут. Поэтому, если 3 x связный 5 x 3 x 4 x для установления простой (или слабой) граф Рис. 3.10. связности графа ориентацию его дуг при- 54 нимать в расчет не следует, то для установления сильной связности это необходимо (см. рис. 3.10). Орграф называется сильно связным, если для любых двух вер шин S x x j i , найдется путь с началом в i x и концом в j x . Для неориентированного графа понятие пути и маршрута совпадают. Теорема 3.1. Для любого графа G либо он сам, либо его дополнение является связным. Доказательство. Пусть G - несвязный граф (см. рис. 3.11), A - одна из его областей G G связности и A G B \ . Тогда для A x и B y в дополнительном графе G есть ре- A B бро y x, , т. е. произвольная вершина из B y y соединена с x маршрутом единичной дли- x x ны, а произвольная вершина из A , отличная Рис. 3.11. от x , соединена с x маршрутом не более чем два, т. е. граф G связен. Рассмотрим i i S S разложение множества вершин графа U S G , на попарно непересекающиеся подмножества, причем такое, что все вершины в каждом i S связаны, а вершины из различных i S не связаны. Тогда можно написать разложение i i i i U S G G , графа G на непересекающиеся связные подграфы i i i U S G , . Такое разложение называется прямым, а сами подграфы называются компонентами связности графа G . Теорема 3.2. Любой граф представляется в виде объединения непересекающихся связных (сильно связных) компонент. Разложение графа на связные (сильно связные) компоненты определяется однозначно. 2 x 3 x 2 x 3 x На рисунке 3.12 изображен орграф, разла- 1 G 2 G 3 G гающийся на три сильно связных компо- 1 x G 6 x 1 x 6 x ненты: подграфы 1 G , 2 G и 3 G . 4 x 5 x 4 x 5 x Рис. 3.12. Теорема 3.3. Пусть U S G , является n -вершинным неориентированным графом с k компонентами связности. Тогда число ребер в таком графе G m удовлетворяет условию 2 1 k n C G m k n , (3.3.1) причем обе эти оценки достижимы. 1 x 6 x Например, на рисунке 3.13 изображен неориентированный граф, у которого 2 , 6 , 7 k m n . Тогда 2 x 3 x 4 x 15 6 5 2 7 2 6 C , т. е. оценка теоремы 3.3 справедлива. 5 x 7 x Рис. 3.13. В различных приложениях теории графов дугам (ребрам) графов, моделирующих реальные процессы, обычно сопоставляются какие-либо числовые характеристики. Например, если дугами изображаются транспортные магистрали, то числовой характеристикой дуги может быть пропускная способность соответствующей магистрали и тому подобное. В таких случаях говорят, что дугам графа приписаны определенные веса. Пусть U S G , - орграф. Если каждой дуге U x x j i , поставлено в соответствие некоторое число j i x x , ω , то граф G называется графом со взвешенными дугами или сетью. 55 При этом вершины графа называются узлами сети. Число j i x x , ω называется весом дуги j i x x , Весом пути μ (длиной, стоимостью и так далее в зависимости от контекста) сети ω G называется число μ , , ω μ ω j i x x j i x x (3.3.2) Понятие сети и веса маршрута для неориентированного графа определяется аналогично. |