Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 47
Текст из файла (страница 47)
Доказательство следуюшей теоремы предоставляется читателю. ТЕОРЕМА 6.54. Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины равна ее степени выхода. ПРИМЕР 6.55. Ориентированный граф на рис. 6.62 имеет эйлеров цикл, так как степень входа каждой вершины равна степени выхода. П ПРИМЕР 6.56. Ориентированный граф на рис. 6.63 не имеет эйлерова цикла, так как степень входа вершины и1 не равна ее степени выхода.
ьз Ь Рис. 6.62 Рис. 6.6З ° УПРАЖНЕНИЯ 1. Среди приведенных ниже графов найдите те, которые имеют эйлеров цикл. 274 ГЛКВА б. Графы, оривнтированныв графы и деревья а) б) в) г) 2. Среди приведенных ниже графов найдите те, которые имеют эйлеров цикл. б) а) 3. Среди приведенных ниже графов найдите те, которые имеют собственный эйлеров цикл. в) Ь с г) Ь РАЗДЕП б.а. Путо и циклы Эйлера 275 б) а) с ~~~3 г) в) О Ь 4. Среди приведенных ниже графов найдите те, которые имеют собственный эйлеров цикл. а) б) а т г) в) а Ь с б.
Какие из следующих графов являются сильно связными? а) б) ь е 276 ГЛАВА б. Графы, ориентироевнныв грвфы и деревья г) в) 6. Какие из следующих графов являются сильно связными? б) а) в) г) 7. Какие из следующих ориентированных графов имеют эйлеровы циклы? а) 6) Раздел а.з. пути и цокпы эйлера 277 г) в) 8. Какие из следующих ориентированных графов имеют эйлеровы циклы? а) б) г) 9. Докажите теорему 6.49. Граф (мультиграф или псевдограф) имеет собственный эйлеров путь тогда и только тогда, когда он связный и ровно две его вершины имеют нечетную степень. 10. Докажите, что если граф содержит цикл от вершины о к ней самой, то он содержит простой цикл от вершины и к ней самой. 11.
Докажите, что ориентированный граф является сильно связным, если в графе существует вершина о такая, что каждая другая вершина графа достижима из о и вершина и достижима из любой другой вершины графа. 12. Докажите теорему 6.54. Ориентированный граф имеет эйлеров путь тогда и только тогда, когда он сильно связный и степень входа каждой вершины равна ее степени выхода. 278 ГЛИНА б.
Графы, ориентироввнныв графы и деревья 6.6. МАТРИЦЫ ИНЦИДЕНТНОСТИ И СМЕЖНОСТИ В этом разделе будут определены две матрицы, связанные с графами: матрицы инцидентности и матрицы смежности. Будет показано, что задание любой из этих матриц дает возможность восстановить граф. Фактически будет показано, что матрица смежности совпадает с матрицей отношения, определенного этим графом.
Как и в случае матрицы отношения для графа, все эти матрицы содержат в качестве элементов 1 или О, поэтому такие матрицы удобно хранить в памяти компьютера. ОПРЕДЕЛЕНИЕ 6.57. Пусть С вЂ” граф. Пусть  — матрица, строки которой обозначены вершинами графа, а столбцы обозначены ребрами графа. Будем считать, что вершины и ребра графа пронумерованы. Элемент г-ой строки и 1-го столбца матрицы В, обозначаемый В... равен 1, если г-ая вершина инцидентна У-ому ребру, и равен О в противном случае. Матрица В называется матрицей инцидентности графа С. ПРИМЕР 6.58.
Пусть С вЂ” граф, изображенный на рис. 6.64, тогда его матрица инцидентности имеет вид, изображенный на рис. 6.65. г'г Уг г, У е~ в! вг еев4 1000 Рис, б.б4 Рис. б.бб ПРИМЕР 6.59. Пусть С вЂ” граф, изображенный на рис. 6.66, его матрица инци- дентности изображена на рис. 6.67. Легко видеть, что степень вершины равна сумме элементов строки, обозначенной этой вершиной, так как каждая единица в этой строке представляет инцидентность этой вершины ребру. В каждом столбце также будут две единицы, так как каждое ребро инцидентно двум вершинам. Можно также включить в рассмотрение матрицы инцидентности для графов с петлями. Вид матрицы инцидентности непосредственно показывает, является ли данное ребро петлей, так как ребро представляет собой петлю тогда и только тогда, когда соответствуюший столбец содержит только одну единицу.
Заметим, что в матрице инцидентности для графа с петлями сумма элементов строки, соответствуюшей данной вершине, не представляет собой степень вершины, если в ней имеются петли. РАЗДЕЛ 6.6. Матрицы инцидентности и смежности 279 е1 вава в4 в5 1 1100 1 0000 0 01 1 0 0 001 1 5 Рис. 6.66 Рис. 6.67 Обратите внимание, что наличие петель ез и ез приводит к тому, что в столбцах, обозначенных этими ребрами, содержится только по одной единице.
и Матрицы инцидентности не имеют большого значения при рассмотрении ориентированных графов, т.к. они не содержат информации о том, как ребро ориентировано. Поэтому, используя матрицу инцидентности, нельзя восстановить ориентированный граф. Такую возможность обеспечивает матрица смежности, определение которой будет сейчас дано. ОПРЕДЕЛЕНИЕ 6.60. Пусть С вЂ” граф (ориентированный граф). Пусть В— матрица, строки которой обозначены вершинами графа и столбцы обозначены теми же вершинами в том же самом порядке.
Элемент с-ой строки и 7-го столбца матрицы В, обозначаемый В;, равен 1, если имеется ребро (ориентированное ребро) из г-ой вершины в 7'-ую вершину, и равен 0 в противном случае. Матрица В называется матрицей смежности графа С. Заметим, что свойства матриц смежности в точности совпадают со свойствами матриц отношения из раздела 4.3. Единственное отличие состоит в том, что используется терминология теории графов, и смысл матрицы смежности интерпретируется для графов. Для матриц смежности включен в рассмотрение также алгоритм Уоршолла. ПРИМЕР 6.61.
Пусть С вЂ” граф, изображенный на рис. 6.68. Его матрица смеж- ности приведена на рис. 6.69. а у! у! уз ч! ча че ч Рис. 6.68 Рис. 6.69 ПРИМЕР 6.62. Пусть С вЂ” ориентированный граф, изображенный на рис. 6.70. Его матрица смежности показана на рис. 6.71. Поскольку петли отсутствуют, все элементы диагонали матрицы равны О. Матрица смежности симметрична, так как граф представляет симметричное отношение. 280 ГЛАВА 6. Графы, ориентированные графы и деревья Рис.
6.70 Рис. 6.71 Очень часто обозначения вершин несущественны. В таких случаях матрицы будут приводиться без обозначений. Например, матрица 1 О О 1 1 О 1 О О О О 1 1 1 1 О является матрицей смежности для ориентированного графа, у которого четыре вершины и восемь ребер. Важным применением матрицы смежности является возможность находить путь фиксированной длины й. Следующий пример дает ключ к пониманию, как это можно сделать. Пусть матрица представляет собой матрицу смежности ориентированного графа С с вершинами оног,оз и иы Рассмотрим матрицу 1 О О 1 1 О О 1 и вычислим, например, элемент Аэ,' = (Аы л Агз)ч (А„л Аз,)ч (Агз л Аз,) 'и (Аы л Ага) = = (1 л О) г <О л О) ~г (О л О) 7 (1 л 1) = =Ононон1= Обратите внимание, что значение Асзз равно 1, так как А,4 и Ага оба равны 1, что означает наличие ребра из вершины ог в вершину о4 и из о4 в вершину оз.
Поэтому из вершины ог в вершину оз имеется путь длины 2. В обшем случае получаем, что А~ = 1 тогда и только тогда, когда имеется такое число й, что 02 А;ь л Аь, = 1, илй, другими словами, имеется ребро из вершины и; в вершину оь А''= [ А= [ 1 О О 1 1 О 1 О О О О 1 1 1 1 О в[ РАЗДЕЛ 6.6. Матрицы инцисентности и сменгности 261 и из иь в вершину и . Поэтому существует путь длины 2 или 2-путь из вершины и, в вершину и,. Но для Аз4 имеем ог Аз4 — (Азг л Аы)ч (Азг л Аг4)ч (Азз л Аз4)'и (Аз4 л А44) = = (Ол1) ь'(ОлО) н(Ол1) и (1лО) = =ООООООО= так что А~4 — — О, потому что не существуют ребра из из в и, и от и, к и4 ни при каком фиксированном г'. Другими словами, не существует 2-путь из вершины иг в вершину иг.
Отсюда следует, что А~э~~ = 1, если имеется 2-путь из вершины и, в вершину и, и А~~г = О, если такой 2-путь не существует. Аналогичным образом, можно убедиться в том, что если использовать обычное умножение матриц, то Аг равно числу значений к таких, что Аиь и Аь оба равны 1, поэтому оно равно числу путей из вершины и; в вершину и длины 2.
Просим читателя, используя индукцию, доказать следующие теоремы. ТЕОРЕМА 6.63. Пусть С вЂ” (ориентированный) граф с вершинами иы иг, из, ..., и„и матрицей смежности А. Путь длины й, или й-путь из и, в и для 1 < к < п существует тогда и только тогда, когда А~~~ = 1. ТЕОРЕМА 6.64. Пусть С вЂ” (ориентированный) граф с вершинами иы иг, из, ..., и„и матрицей смежности А. Из вершины и, в вершину и, имеется гп путей длины й, где 1 < й < и тогда и только тогда, когда А," = гп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
