Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 18
Текст из файла (страница 18)
При изображении ориентированных графов (рис. 4.2, а — з) направления ребер отмечаются стрелками, примыкающими к их концам. Ориентированный граф также может иметь кратные ребра (рис. 4,2, е), петли (рис. 4.2,Ж), а также соединяющие одни и те же вершины ребра, идущие в противоположных направлениях (рис. 4.2, з). др Юр зр др зр акр зр Каждому неориентированному графу можно поставить в соответствие ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющими противоположные направления, Такое соответствие будем называть каноническим, Матрица ннцидентности и список ребер, Задать граф— значит описать множества его вершин и ребер, а также от.
ношение инцидентности. Когда граф 6 — конечный, для описания его вершин и ребер достаточно их занумеровать. Пусть о„ом .„, о„— вершины графа 6; еь еь ..., е — его ребра. Отношение инцидентности можно определить матрицей ~~е;Д, имеющей и строк и и столбцов. Столбцы соответствуют вершинам графа, строки — ребрам, Если ребро е~ инцидентно вершине оь то еп=1, в противном случае ец= =О. Это так называемая матрица инциденгности неориентированного графа 6, которая является одним из способов его определения (для графа на рис. 4.3 она дана в табл.
4.1, а). В матрице инцидентпости ~~з~ф ориентированного графа 6, если вершина о; — начало ребра аь то ео= — 1; если пр — конец ац то ю;=1; если а; — петля, а ор — инцидент- Таблица 4,! П Ри !ЧЧ Ч!ЧИ и и!!чч ч)чи ооо ооо ооо о о о)о о о О О 2 — о о — о ! о о ! о ! о о — ! о ΠΠ— 1 ΠΠΠ— 1 О о о о о а) Ребра Вершины Вершнны Ребра 1~ П 1, И! И, )Ч П1, Ч Ш, Ч) И). ЧИ чи, чи г) в) ная ей вершина, то во=ай, где х — любое число, отличное от 1, О и — 1,'в остальных случаях еп О (пример — табл.
4.1, б для графа на рис. 4.4). В каждой строке матрицы инцидентности для неориентированного или ориентированного графа только два элемента отличны от О (илн один, если ребро является петлей). Позтому такой способ задания графа оказывается недостаточно зкономным. Отношение инцидентности можно еще задать списком ребер графа, Каждая строка зтого списка соответствует ребру, в ней записаны номера вершин, инцидентных ему. Для неориентированного графа порядок зтих вершин в строке произволен, для ориентированного первым стоит номер или другое наименование начала ребра, ! 2 з 5 6 7 8 9 )О о о О)О о о о ! о о о о о ооо ооо ооо 1 г 3 4 5 6 7 в 9 !о о о о о о о о о о о о о ! о о о о ! о о о о о ! о о о ° ! о о ! о о о 1, И 1, И) И', 1Ч 1' ,Ч И,' Ч) П),' !Ч И!, Ч 1Ч, Ч! ч, 'чи Ч), ЧИ а вторым — его конца, В табл.
4.1, в и 4.1, г приводятся списка ребер для графов, изображенных на рис. 4.3 и 4.4. По списку ребер графа легко построить его матрицу инцидентности, Действительно, каждая строка этого списка Рид 4.3. Рис, 4.4 соответствует строке матрицы с тем же номером. Для неориентированного графа в строке списка указаны номера элементов строки матрицы инцидентности, равные 1, и для ориентированного графа в этой строке первым стоит номер элемента строки матрицы, равного — 1, а вторым— номер элемента, равного +1. Матрица смежности графа. Это квадратная матрица (В,Д, столбцам и строкам которой соответствуют вершины графа. Для неориентированного графа бц равно количеству ребер, инцидентных 1-й и )ьй вершинам, для орйептированного графа этот элемент матрицы смежности равен количеству ребер с началом в 4-й вершине и концом в /-й. Таким образом, матрица смежности неориентированного графа симметрична (бп=бп), а ориентированного — не обязательно.
Если она все же симметрична, то для каждого ребра ориентированного графа имеется ребро, соединяющее те же вершины, но идущее в противоположном направлении. Ориентированный граф с симметричной матрицей смежности канонически соответствует неориентированному графу, имеющему ту же матрицу смежности. Матрицы смежности рассмотренных ранее графов (рис, 4.3, 4.4) приводятся в табл. 4.2.
Матрица смежности также определяет соответствующий неориентированный нли ориентированный граф. Число его 92 Таблица 4.2 1 !! !!! !Ч Ч Ч! Чп и Ш !Ч Ч Ч! ЧП о о о о о о 1 1 1 о о о о о о о о о о о О1! О ооо ооо о ооо о ооо о ооо о ооо о О ! 1 О о о о о о ! ! о О ! О О ! О о о о о о о о ! о о о О ! О о о о о 1 1 О ! П !!! 1Ч Ч Ч! Ч!1 ! 1! 1И !Ч Ч Ч! Ч!1 93 вершин равно размерности матрицы и, 1-й н 1-й вершинам графа инцндентны бн ребер.
Для неориентированного графа бц=би и все его ребра определи!отся верхним правым треугольником матрицы, расположенным над диагональю, включая последшою. Количество их равно сумме бп по этому л л ~ треугольнику, т. е. У '~~ бсь Ребра ориентированного графа ~'=1 1=! определяются всеми элементами бц матрицы смежности. В обоих случаях по матрице смежности легко строится, например, список ребер, определяющий граф. Элементу матрицы смежности, расположенному в Рй строке и !'-м столбце, соответствуют.б, строк списка ребер !при бн=Π— нн одной строки), в каждой из которых записаны номера 1, 1. Для неориентированного графа эти строки соответствуют только элементам описанного ранее верхнего правого треугольника матрицы смежности, т. е.
элементам бц с 1)1, а для ориентированного графа нужно рассматривать все элементы бп. Идентификация графов, заданных своими представлениями. Итак, граф может быть представлен различными способами. Он может быть изображен на чертеже, задан матрицей ипцидентности, списком ребер нлн матрицей смежности.
Вид чертежа зависит от формы линий н взаимного расположения вершин: Иногда не так легко понять, одинаковы лн графы, изображенные разными чертежами 1ср., например, графы на рис. 4.5). Внд матриц н списка ребер зависит от нумерации вершин и ребер графа. Строю говоря, граф считается полностью заданным„если нумерация его вершин зафиксирована; графы, отличающиеся только нумерацией вершин, называются изоморфными, Перенумерация верши~ графа задается строкой а1, аъ ... ... и новых номеров вершин, расположенных в исходном порядке. Новая матрица смежности получается из исходной перемещением каждого элемента бо в и1-ю строку и а1-й столбец, т. е, в результате перестановки (а1, с22, ..., а ) строк и столбцов исходной матрицы.
Поэтому, чтобы узнать, представляют ли две матрицы смежности изоморфпые графы, можно, например, произвести всевозможные одинаковые перестановки строк и столбцов первой матрицы. Если после одной из этих перестановок возникнет матрица, тождественно совпаРис. 4.5 дающая со второй, графы, изображаемые данными матрицами смежности, изоморфны. Однако чтобы убедиться таким способом в том, что графы неизоморфны, придется выполнить все и! перестановок строк и столбцов, что является достаточно трудоемкой операцией.
Матрица инцидентности графа и список его ребер зависят от нумерации ребер и вершин. Переход от одной пары нумерации к другой определяется перестановками (ин а2, ..., 12, ) вершин и (р1, б2, ..., р ) ребер рассматриваемого графа. Матрица инцидентности получается из первоначальной в результате перестановки строк (2'-я — на б,-е место) и столбцов Ц-й — на и;-е).
Строки списка ребер переставляются так же, как и строки матрицы инцидентности, й каждый номер 4 в строках списка заменяется номером а1. Графы без кратных ребер. Пусть даны два множества У1 и )22. Их прямое произведение г'1Х'г2 можно симметризовагь, т. е. рассматривать также пары (о2, о,), где о2енР2, а о1~)1ь пРичем паРы (оь о,), и (оь и1) считаютсЯ одинаковыми. Если У1= Г2='г', то несимметризованное произведение уХр — это множество всех упорядоченных пар (о1, и2) элементов множества Р, а симметризованное произведение ~Р)~Р1 — это множество неупорядоченных пар, когда (о1 о2) (о2 ш). Пусть Š— подмножество [РХР). Тогда г' можно считать множеством вершин, а Š— множеством ребер неориентированного графа [ребро (сн о2)епЕ инцидентно вершинам о, и оД.
Аналогично подмножество Е'с: 21Х)1 определя 94 ет ориентированный граф, в котором началом ребра (он оз)енЕ' является вершина по а концом — вершина э,. Каждая пара (оо оз), принадлежащая подмножеству Е или Е', фигурирует в качестве ребра только один раз, следовательно, построенные графы не имеют кратных ребер, и наоборот, если граф не имеет кратных ребер, то последние однозначно определяются неупорядоченной или упорядоченной парой (оь оз) инцидентных им вершин.
Поэтому множества ребер неориентированного или ориентированного графа считаются подмножеством в первом случае симметризованного произведения, а во втором — несимметризовапного. Степени вершин графа. Пусть б — неориентированный граф. Количество р(о) ребер, инцидентных вершине ое-:6, называется ее локальной степенью или просто степенью.
Если степени всех вершин конечны, рассматриваемый граф б называется локально-конечным. В частности, любой конечный граф локально-конечен. Когда заданы матрицы смежности или инцидентности графа, можно определить локальные степени всех его вершин. Действительно, в )чм столбце, соответствующем вершине оп единицы стоят на пересечении со строками, которым соответствуют инцндентные этой вершине ребра, а остальные элементы столбца равны О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
