В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU), страница 2

Например, в неориентированном графе на рис. 1.1 степень вершины 3 равна 2, степени остальных вершин равны 4. Теорема 1.1. Пусть в графе С р вершин и с» ребер. Пусть спец ь; --- степень вершины, лэ;. Тогда ~ ~с1е и; = 2д. э=л Докслзательство. Когда мы считаем степень одной вершины, мы считаем все ребра, выходящие из нее. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается дважды, так как оно инцидентно двум вершинам (петллл ио определению степени также посчитаются дважды). Поэтому общая сумма будет равна удвоенному числу ребер. В ориентированном графе можно определить степень так же„как в неориентированном графе, если не учитывать ориентацию. Кроме этого, для ориентированных графов вводится следующее определение.

Определение. Полустетэенью исхода 0 (в) (полустеьзенью захода сУ~~лэ)) вершины в в ориентированном графе называется число дуг, выходящих из данной вершины (соответственно входящих в данную вершину). Легко видеть, гго в любом ориентированном графе выполняется равенство р р сне~ (с;) = 2 с1ер;+(г;). ~=1 с=! поскольку в обеих частях равенства каждая дуга учитывается ровно 1 раз. Для человека удобно геометрическое представление графа, такое, например, как на рис 1.1.

В компьютере используют другие, "более дискретные", способы представления графов. Один из наиболее распространенных способов представление графа магрицей смежности. Определение. Пусть граф С имеет р вершин и пусть его вершины занумерованы числами 1,2,...,р. Матрица с р строками и р столбцами называется митрицей смеясносгви, графа С, если для любых 1ср и 1дг а~с, Я равно числу ребер (дуг), идущих из ве1ппины К в вершину 1. Например, графы, изображенные на рис. 1.1, представляются следующими матрицами смежности. 1 1 0 1 1012 О 101 1210 1 1 0 1 0010 0001 0200 При представлении графа махрицей смежности легко выполняюгся операции добавления или выбрасывания ребра (соответствующий элемент матрицы просто увеличивается или уменьшается на 1), легко считается степень вершины г (достаточно просуммировать числа в к-ой строке, диагональный элемент взяв дважды).

В целом, матрицы смежности очень удобны. Однако, если в графе мало ребер, то представление графа матрицей смежности может быть не очень хорошим. Например, если в графе 50 вершин, то матрица будет иметь 2500 элементов, хотя в графе может оказаться лишь несколько сотен ребер. В таких случаях используют списки смелсиослмй. Для каждой вершины образуется список, в когорый заносят все ве1ппины, в которые из данной вершины идут ребра (дуги). Например, графы, изображенные на рис. 1.1, представляюхся следующими списками смежностей 1: 1, 2. 4; 1: 1.

2> 4; 2: 1, 3, 4, 4; 2: 3; 3: 2, 4; 3: 4; 4: 1> 2, 2, 3. 4: 2, 2. При представлении графов списками смежностей и щ>лл динамическом изменении графов необходимо использовать алгоритмы работы со списками, что хорошо реализуется в ряде алгоритмических языков. При изучении структуры графов некоторые графы можно не различагь. Определение. Пусть Сл = (1~>> Ел) и С> = (1'~, Е2) -- два графа. Тол>да Сл и С~ называются изоморфными, есл>л существуют взаимно однозначные отображения >рл . Гл -+ 1'>, р> . Е> — ~ Е2 такие, что для любого ребра (дуги) (ци) Е Е выполняется д>(и, в) = (рл(и), рл(в)).

Другими словами, соответствующие ребра должны соединять соответсгвуюлцие вершины. Для графов без петель и кратных ребер зто определение эквллвалентно следующему более простому определению. Определение (для графов без петель и крагных ребер).

Графы Сл — — (1'л, Ел) и С> — — (Ъ~,Е>) называются изомврфкнми, если существует взаимно однозначное отображение д: 1'> — ~ 1::> такое, что (н, >>) >= Ел ~=> (>р(и), >р(л>)) >= Ег. Рассмотрим теперь некоторые понятия, связанные с внутренней структурой графа. Определение. Граф Сл = (1 >, Ел) называется иодграфом графа С = (г",.Е), если 1'л С 1' и Е> С Е.

Определение. Пугивм в графе (орграфе) С = (1г, Е) называется последовагельносгь вершин и ребер (дуг) вида ~0 > (>>О в1); '»л > ° ° °; ~» — 1 > (»» — л > >>») > вп где все в; Е Е и все (в;, л>;+>) Е Е. Длина л>утии — нто число ребер (дуг) в нем. Говорят. что зтот путь идет из л>о в е„. Х(вин зто путь без повторяюлцихся ребер (дуг), простая цепь — — путь без повторяющихся вершин. Лемма 1.1. ХХз л>вбого пути, идущего ллз г>в в л»„, гдв»о ф л>„, мвз>сно выделилиь иодиуть ллв гв в и,> являющийся простой цетинья.

Докизигиельсгиво. Пусть данный путь --- не простая цепь. Тогда в нем повторяется некоторая вершина в, то есть он имеет вид: Рл = гоС>г>С2гСзв,. Тогда он содержит подпуть Р> = АТОС>л>Сзл>„. Если в Р> нов горяегся нРКОГОрая Ве|)шина, 'Го анн ВОГичнО удалим Рще кусОк и т. д. Процесс должен закон*(и(ься, т. к. Р1 — конечный нугь. Определение. Пугь называется загикиутым, если е„= ив. Пугь называет'ся циклОА(. если Ра = ив и ~)еб~)а «дуГи) не НО)иго~)як)'гс11. Пугь называется простым циклом, если 1:.„= Ро и болыие нет повторений вершин. Дале~ нод гра(1)ом будут ноннмг((ься только конечны(' нео1)иентированные графы. Определение.

Граф С = «1'; Е) называеття ()аягным, если для любых двух Вершин и;, и б 1Г в с' существует путь из ('; в а.. Отношение "суьцествует путь из ве1)н)ины е В вершину а' в графи (т' является очношением эквивалентности на множестве вершин. Поэтому, если гра()) () не связный то его Вершины можно разбихь на несколько подмножеств так, что ве1)нн(ны в одном н гом же множестве мОжнО соедин!Ггы!угем, и ВР$)н(ины из ~)азных множ(.',("Гв нельзя сОРдиннгь пугем. Каждое:такое множество вершин Вместе с ребрами графа С', соединяющими зги ве1янины, называется с()лзно(1 кол(т)онентт)ой графа С. Так, нанример, граф на рис.

1.2 имеет 3 связных кокшоненты. Рис. 1.2. Дока)кем те(гарь г(Р(.колько всномогеггельных ) тверждений связно(:1 и и цик;1ах, кого!)ЫР ног~)ебук)гся нам в дй.:1ы(ей(нем. Лемма 1.2. Е(ли граф С = «1, Е) еалзный и а Е Г, 6 б р, а, ф 6, и «а,6) ф Е. то тири добаалеиии к графу с). ребра «а.,6) а полу (енном граф(. будет() тц>остоИ х(икл.

Доказатт)ельстт(ао. Так как с)' — связный граф, то в нем есть путь из а в 6. Тогда по лемме 1.1 В С есть простая цепь С из а в 6. Поэтому в полученном графе есть цикл С. «6„а), а. Лемма 1.3. Если граф 6 = «1', Е) салзньИГ и рефо «а,,6) соде))- жмтг)сл а некотором цикле и графе су, тдо т(т)и аыбрасы((ании из г1)афа С реб1)а «а,6) сноаа т)ол(гчитх)ея сйязиы(1 гт)аф. Доказательство. Это утверждение следуех из того, что нри выбрасывании из графа (г ребра «а,6) вершины а и 6 все равно остаются в одной связной компоненте, поскольку из а в 6 можно пройти но оставшейся час Ги цикла. Лемма 1.4. Пусть в графе С = (К Е) р вершин, и а ребер. Тогда в С не менее р — а связных иомпоненгп.

Если при этим в С непг циклов, то С состоит ровно из р — а связных компонент. Догсазательство. Пусть к некоторому графу Н, содержащему вершины и, и, добавляется ребро (и,и). Тогда если и. и лежат в разных связных компонентах графа Н, то число связных компонент уменьшится на 1. Если и, и лежаг в одной связной компоненте графа Н, то число связных компонент не изменится. В любом случае число связных компонент уменьшается не более чем на 1. Значит при добавлении д ребер число связных компонент уменьшается не более чем на а. Так как граф С получается из графа Сг = (1:;) добавлением гг ребер, то в С не менее р — а связных компонент.

Пусть теперь в С нет циклов, и пусть в процессе получения С из Сг добавляется ребро (и, о). Если бы и, и лежали уже в одной связной компоненте, то в С, согласно лемме 1.2, возникал бы цикл. Следовательно, и, и лежат в разных связных компонентах и при добавлении ребра (и,и) число связных компонент уменьшается ровно на 1. Тогда С состоит ровно из р — гг связных компонент. Следствие. Если др — 2, то лгобоЬ граф с р вершинами и гг ребрами не связен. Доказательство. По лемме 1.4 число связных компонент не менее р — д2. Если граф С с р вершинами задан магрицей смежности Л, то быстрое нахождение связных компонент можно осуществить следующим образом.

Рассмотрим матрицу 1г порядка р, в которой на диагонали стоят 1, 1г(г, г) = 1, если а(г, г) > О и 1г(г,Я = О, если а(г, г) = О. Тогда равенство 1г(г,Я = 1 равносильно тому, что из вершины с номером г в вершину с номером г' существует путь длины не более 1. Определим теперь матрицу 1г. порядка р, в которой 1г.(г,', г) = 1 тогда и только гогда, когда из вершины с номером г в вершину с номером г суьцествует путь длины не более 1. Легко понять, что все матрицы Хг при Йр — 1 совпадают и злемент с номером (г, г) в них равен 1 тогда и только тогда, когда из вершины с номером г в вершину с номером г существует хотя бы один путь.