Рис. 7.1
II. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
§ 7. Основные определения и типы графов
1. Основны е понятия
Пусть V – конечное непустое множество и Е {{u , v } u ,v V , u ≠ v } – множество его двухэлементных подмножеств. Пара G = (V, E ) называется графом . Множество V = V (G ) при этом называется множеством вершин графа G, а его элементы – вершинами; множество Е = Е (G ) называется множеством ребер графа G , а его элементы – ребрами. И вершины, и ребра графа G называются его элементами. Поэтому если u – вершина графа G , а е – ребро G , то вместо u V (G ), e E (G ) можно писать u G , e G .
Если e = {u , v } – ребро графа G (пишут также е = uv ), то вершины u и v называются концами ребра е .
Графы удобно изображать в виде рисунков, на которых вершинам соответствуют отмеченные точки (или кружочки), а ребрам – непрерывные линии, соединяющие соответствующие вершины (см. рис. 7.1).
Вершины u и v графа G называется смежными , если {u , v } E (G ), т.е. если они соединены ребром. Два ребра, в свою очередь, называются смежными , если они имеют общий конец. Если вершина v является концом ребра e , то v
и e называются инцидентными .
Мощность V (G ) множества вершин V (G ) называется порядком графа G и обозначается G . Если V (G ) = n и E (G ) =m , то граф G называется (n,m ) -графом .
2. Основные типы графов
Граф называется пустым , если E (G) = , т.е., если в нем нет ребер. Пустой граф порядка n обозначается 0 n . Граф 0 1 называется тривиальным . Граф, в котором любые две вершины соединены ребром, называется полным . Полный граф порядка n обозначается K n (рис. 7.2 – 7.5).
Граф такого вида, как на рис. 7.6, называется простой цепью . Простая цепь порядка n обозначается P n (на рис. 7.6 изображена цепь P 4 ). Простая цепь P n имеет n – 1 ребер.
Рис. 7.9
Замкнутые цепи, т.е. такие графы как на рис. 7.7, называются простыми циклами . Простой цикл порядка n обозначается C n (на рис. 7.7 изображена простая цепь С 7 ). Понятно, что простая цепь C n имеет столько же ребер, сколько и вершин, т.е. n .
Графы, такие как на рис. 7.8, называются колесами. Колесо порядка n +1 обозначается W n (на рис. 7.8 изображено колесо W 7 ); оно имеет 2n ребер.
Граф называется двудольным , если множество его вершин можно разбить на два непустых подмножества (доли) так, что никакие две вершины одной доли не являются смежными. (Аналогично определяются трехдольные, четырехдольные и т.д. графы.) Таким образом, в двудольном графе смежными могут быть только вершины из разных долей (не обязательно каждая с каждой). Пример двудольного графа см. на рис. 7.9.
Если же в двудольном графе любые две вершины из разных долей соединены ребром, то такой граф называется полным двудольным .
Полный двудольный граф с n вершинами в одной доле и с m вершинами – в другой обозначается K n,m . См. примеры, приведенные на рис. 7.10 – 7.12.
K 2,2 |
K 2,3 |
K 3,3 |
||||
Графы K 1, n называется звездными графами, или звездами.
Легко видеть, что граф K n,m является (n+m, nm )- графом, т.е. имеет n+m вершин и nm ребер.
Понятно, что существуют графы, которые можно одновременно отнести к нескольким типам. Например, K 3 = C 3 , K 2 = P 2 , K 2, 2 = C 4 , K 4 = W 3 .
3. Обобщения понятия графа
Определение графа в п.1 предполагает, что любая пара вершин может быть соединена не более, чем одним ребром. Однако, существуют задачи и примеры графов,
Рис. 7.16
когда необходимо допускать существование нескольких ребер между одной и той же парой вершин. Такие ребра называются кратными . Граф с кратными ребрами называется мультиграфом (рис. 7.14). Графы, соответствующие исходному определению (в тех случаях, когда нужно подчеркнуть, что в них отсутствуют кратные ребра), называются простыми графами (рис. 7.13). Кроме того, порой приходится рассматривать ребра вида {v, v }, соединяющие вершину v саму с собой. Такие ребра называются петлями . Мультиграф с петлями называется псевдографом (рис. 7.15.).
Пара (V , E ), где V – непустое множество, а E V 2 , называется ориентированным графом (или кратко: орграфом ). Ребра такого графа представляют собой ориентированные (т.е. упорядоченные) пары вида
(u , v ). При этом, вершина u называется началом ребра , а v – концом . Ориентированные ребра называются дугами и изображаются в виде линий со стрелками, указывающими направление от начала ребра к концу
Дуги (u , v ) и (v , u ), соединяющие одну и ту же пару вершин, но имеющие противоположные направления, называются симметричными .
Можно рассматривать не только простые орграфы, но также ориентированные мульти- и псевдографы.
Иногда при решении некоторых задач ребрам и (или) вершинам ставят в соответствие некоторые числа. Независимо от их конкретного смысла, такие числа называют весами (вес вершины, вес ребра), а полученный граф называется взвешенным графом .
Как правило, при изучении тех или иных вопросов, заранее оговаривается (или ясно из контекста) о каких графах идет речь. В этом случае их просто называют графами без приставок "мульти-", "псевдо-" и т.д.
4. Изоморфные графы
Одной из особенностей графов является то, что при их изображении на плоскости совершенно не важно, как расположены вершины друг относительно друга. Поэтому одному и тому графу могут соответствовать различные его изображения. Кроме того, именно такие рисунки, представляющие собой простейший способ задания
графа, зачастую и называют графами. Чтобы отличать рисунки, отвечающие одному и тому же графу, от рисунков, изображающих различные графы, введем следующее понятие.
Определение . Два графа G и H называются изоморфными , если существует биекция f : V (G ) → V (H ), сохраняющая смежность, т.е. такое биективное отображение, при котором образы вершин v и u графа G смежны в H тогда и только тогда, когда u и v смежны в графе G . Отображение f , обладающее указанным свойством, называется
изоморфизмом.
Если графы G и H изоморфны, то пишут G H .
Например, все три графа на рис. 7.17-7.19 изоморфны друг другу (изоморфизм определяется нумерацией вершин).
Очевидно, что отношение изоморфности на множестве графов является отношением эквивалентности (оно рефлексивно, симметрично и транзитивно). Следовательно, множество всех графов разбивается на классы изоморфных графов так, что разные классы не пересекаются. Все графы, попадающие в один класс естественно отождествлять, т.е. считать совпадающими (они могут отличаться лишь рисунком или природой своих элементов). В тех случаях, когда нужно подчеркнуть, что рассматриваемые графы отличаются лишь с точностью до изоморфизма, принято говорить об "абстрактных графах ". По сути дела, абстрактный граф – это класс изоморфных графов.
В некоторых ситуациях все же приходится различать изоморфные графы и тогда возникает понятие "помеченный граф ". Граф порядка n называется помеченным, если его вершинам присвоены метки, например, номера 1, 2, 3, …, n . В этом случае вершины графа G отождествляют с их номерами, т.е. полагают, что V (G ) = {1, 2, 3, …, n }.
Учебный проект: Его высочество граф математический/
Виды графов
Плоские графы
Граф называется плоским (планарным)
, если его можно уложить на плоскости так, чтобы его ребра нигде не пересекались, кроме как в вершинах. Имеется два основных непланарных графа - Г5 и Г3,3, изображение которых дано на рисунке. Оба графа Г5 и Г3,3 являются регулярными
, но последний относится еще и к так называемому двудольному
, который определяется здесь как многозначное отображение трех верхних вершин на три нижние вершины, или наоборот. В общем случае в двудольном графе Г3,3 число вершин в обоих рядах может быть любым.
Двудольный граф
Двудольный граф (или биграф, или чётный граф)
- это граф G(V,E), такой что множество вершин V разбито на два непересекающихся подмножества V1 и V2, причём всякое ребро E инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2). То есть, правильная раскраска графа двумя цветами. Множества V1 и V2 называются «долями»
двудольного графа. Двудольный граф называется «полным»
, если любые две вершины из V1 и V2 являются смежными
. Если |V1|=a,|V2|=b , то полный двудольный граф обозначается Ka,b.
Изоморфный граф
Изоморфизм
- это очень общее понятие, которое употребляется в различных разделах математики. В общих чертах его можно описать так: Пусть даны два множества с определённой структурой (группы, кольца, линейные пространства и т. п.). Биекция между ними называется изоморфизмом, если она сохраняет эту структуру. Такие множества со структурой называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких множеств со структурой.
Два графа G=(X,U) и L=(X",U") являются изоморфными
, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.
Пример: следующие графы, приведенные на рисунке, изоморфны:
Псевдограф
Псевдограф
– граф с кратными ребрами и петлями.
Пример: пусть D=(V,X) – ориентированный граф, V={V1,V2},X={x1={V1,V2},x2={V1,V2],x3={V1,V2},x4={V2,V2} .
Тогда D=(V,X) – ориентированный псевдограф
Мультиграф
Мультиграф
– граф, в котором имеются кратные (параллельные) ребра.
Мультиграф
– это псевдограф без петель.
Пример: пусть D=(V,X) – ориентированный граф,V={V1,V2} ,X={x1={V1,V2},x2={V1,V2}} . Тогда D=(V,X)– ориентированный мультиграф.
Сформулировано понятие «граф» и сети. Выделены его составные части: вершины и ребра. (Слайд 3)
Граф - это набор узлов (вершин) и связей между ними (ребер).
Сеть – граф, в котором вершины связаны между собой по принципу «многие ко многим»
Как представить информацию о графе в памяти компьютера? Хранить ее в виде рисунка (растрового или векторного) неэффективно, потому что рисунок предназначен для восприятия человеком, а не компьютером. Компьютеру удобнее всего хранить информацию в виде таблиц (массив тоже можно считать простейшей таблицей). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования). Если, например, на пересечении строки A и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B ; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности. На рисунке показаны схема дорог, соответствующий ей граф и его матрица смежности: (слайд 4)
Единица на главной диагонали (выделенной серым
цветом) показывает, что в графе есть петля
-ребро,
которое начинается и заканчивается в одной и той
же вершине.
Обратите внимание, что матрица смежности
симметрична относительно главной диагонали, то
есть если существует ребро из вершины A
в
вершину B
, то существует и ребро из B
в
A
. Такой граф называют неориентированным
- ребра не имеют направления и каждое из них
учтено в матрице смежности дважды. Матрица
смежности не дает никакой информации о том, как
именно расположены узлы друг относительно друга.
Для таблицы, приведенной выше, возможны,
например, такие варианты, как на рисунках. (слайд
5)
Если для каждого ребра указано направление, граф называют ориентированным (или орграфом). Ребра орграфа называют дугами. Его матрица смежности не всегда симметричная. Единица, стоящая на пересечении строки A и столбца B, говорит о том, что существует дуга из вершины A в вершину B: (слайд 6).
Часто с каждым ребром связывают некоторое число - вес ребра. Это может быть, например, расстояние между городами или стоимость проезда. Такой граф называется взвешенным. Информация о таком графе хранится в виде весовой матрицы, содержащей веса ребер: (слайд 7).
У взвешенного орграфа весовая матрица не всегда симметрична относительно главной диагонали: (слайд 8).
Если связи между двумя узлами нет, на бумаге можно оставить ячейку таблицы пустой, а при хранении в памяти компьютера записывать в нее условный код, например, 0, –1 или очень большое число (?), в зависимости от задачи.
Другим примером ориентированного графа являются блок-схемы алгоритмов. (слайд 9) Блок-схема алгоритма представляет собой граф процесса управления некоторым исполнителем. Блоки – вершины этого графа – обозначают отдельные команды, которые отдаются исполнителю, а дуги указывают на последовательность переходов от одной команды к другой.
Определения
Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения - наиболее часто встречаемые.
Граф
Граф или неориентированный граф G - это упорядоченная пара G : = (V ,E )
- V это множество вершин или узлов ,
- E это множество пар (в случае неориентированного графа - неупорядоченных) различных вершин, называемых рёбрами .
V (а значит и E ) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов . Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | - порядком , число рёбер | E | - размером графа.
Вершины u и v называются концевыми вершинами (или просто концами ) ребра e = {u ,v } . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними .
Два ребра называются смежными , если они имеют общую концевую вершину.
Два ребра называются кратными , если множества их концевых вершин совпадают.
Ребро называется петлёй , если его концы совпадают, то есть e = {v ,v } .
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной
, если она не является концом ни для одного ребра; висячей
(или листом
), если она является концом ровно одного ребра.
Ориентированный граф
Ориентированный граф (сокращённо орграф ) G - это упорядоченная пара G : = (V ,A ) , для которой выполнены следующие условия:
- V это множество вершин или узлов ,
- A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами .
Дуга - это упорядоченная пара вершин (v, w) , где вершину v называют началом, а w - концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w .
Смешанный граф
Смешанный граф G - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой G : = (V ,E ,A ) , где V , E и A определены так же, как выше.
Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.
Прочие связанные определения
Путём (или цепью ) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Ориентированным путём
в орграфе называют конечную последовательность вершин v
i
, для которой все пары (v
i
,v
i
+ 1)
являются (ориентированными) рёбрами.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер . Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u ,v ,u ) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
Путь (или цикл) называют простым , если ребра в нём не повторяются; элементарным , если он простой и вершины в нём не повторяются. Несложно видеть, что:
- Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
- Всякий простой неэлементарный путь содержит элементарный цикл .
- Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
Более абстрактно, граф можно задать как тройку , где V и E - некоторые множества (вершин и рёбер , соотв.), а - функция инцидентности (или инцидентор ), сопоставляющая каждому ребру (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов ). Частными случаями этого понятия являются:
Под данное выше определение не подходят некоторые другие обобщения:
- гиперграф - если ребро может соединять более двух вершин .
- ультраграф - если между элементами x i и u j существуют бинарные отношения инцидентности .
Литература
- Оре О. Теория графов. М.: Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu
- Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu
- Харари Ф. Теория графов. М.: Мир, 1973. http://eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu
- Кормен Т. М.и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс» , 2006. - С. 1296. - ISBN 0-07-013151-1
- Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. - М.: Физико-математическая литература, 1997. - ISBN 5-02-015033-9
- Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
- Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. - 168 c.
Лекция 4. Графы
4.1.Графы. Определение, виды графов
4.2. Свойства графов
Программные положения
Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых - теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков. (Ф.Харари «Теория графов»)
Обратите внимание на удобство и возможность широкое использования графов в прикладных задачах
Литература
Контрольные вопросы
- Что такое граф?
- Что называют вершиной и ребром графа?
3. Можно ли обвести данную схему, не отрывая карандаша и не проходя дважды никакие ребра
- Может ли сумма степеней вершин графа быть нечетным числом?
- Можно ли организовать турнир между 11 командами, так, чтобы каждая сыграла ровно 5 матчей?
6. Покажите равносильность определений из п.4.1.(6) (что описывают один и тот же объект)
7.Покажите, что изоморфны графы
8. Покажите, что изоморфизм есть отношение эквивалентности на графах.
9.На какое минимальное количество частей нужно разделить кусок проволоки, чтобы из нее можно было сделать каркас куба
10. Покажите, что граф является планарным
Графы. Определение, виды графов
Отцом теории графов является Л.Эйлер A707-1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов.
В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рис. 4.1.(1) (A,D – острова, B,C – берега реки). Задача состояла в следующем: найти маршрут прохождения всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей. Л.Эйлеру удалось найти решение этой задачи заключается в доказательстве невозможность такого маршрута.
Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки. Получился «граф». Этот граф показан на рис. 4.1.(2), где точки
отмечены теми же буквами, что и четыре части суши на рис. 4.1(1). Утверждение о несуществовании «положительного» решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рис. 4.1(2).
В таком случае задача приобретает следующую формулировку: начиная с любой вершины, проходя по каждому ребру только один раз, вернуться в исходную вершину.
Примером другой проблемы, которую можно промоделировать на основе теории графов, является задача о снабжении трех домов тремя видами коммунальных услуг. Согласно условию задачи к каждому из трех домов необходимо подключить три вида коммунальных услуг, например, воду, газ и электричество, посредством подземных линий труб и кабелей. Вопрос состоит в том, можно ли обеспечить эти три дома коммунальными услугами без пересечения линий снабжения. Граф, моделирующий данную задачу, показан на рис. 4.1(3) (Эта известная модельная задача иногда формулируется как задача про дома и колодцы)
Аналогичная задача более практического характера возникает при создании микросхем. В них пересечение проводов на каждом уровне является нежелательным.
Определение 4.1(1)
Граф есть конечное множество V, называемое множеством вершин, и множество Е двухэлементных подмножеств множества V. Множество Е называется множеством ребер. Элемент множества Е называется ребром. Граф обозначается G(V, E). Элементы а и b множества V называются соединенными, или связанными ребром {а, b}, если .
Иначе говоря, граф – это схема, состоящая из точек, некоторые из которых соединены отрезками.
Примерами графов являются схема метро, генеалогическое дерево, карта автомобильных дорог и др.
Определения 4.1(2)
Если {а, b} - ребро, тогда вершины а и b называются концами ребра {а, b}. Ребро {а, b} называют также инцидентным к вершинам а и b. Обратно, говорят, что вершины а и b инцидентны к ребру {а, b}. Две вершины называются смежными (соседними ), если они являются концами ребра, или, что то же самое, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.
Если разрешено наличие нескольких ребер между двумя точками, граф называется мультиграфом.
Если в графе все вершины соседние, граф называется полным .
Граф с одной вершиной и без ребер (состоящий из 1 точки – вершины), называется тривиальным.
Определение 4.1(3)
Степенью вершины v обозначается deg(v), называется количество ребер, инцидентных этой вершине (исходящих из нее).
Вершина степени 0 (то есть из вершины не исходит ни одного ребра, это «одинокая» точка) называется изолированной.
Вершина степени 1 называется висячей.
Вершины могут быть четными и нечетными.
Определения 4.1.(4)
Путь (между вершинами) – последовательность ребер и промежуточных вершин, их соединяющая
Длина пути – количество ребер, входящих в путь
Простой путь – путь, в котором все ребра и вершины различны
Цикл (петля) – замкнутый путь ненулевой длины, в котором все вершины различны кроме начала, совпадающего с концом
Примеры 4.1(1).
1. Граф с множеством вершин V = {а,b,с} и множеством ребер Е {{а, b}, {b, с}} может быть изображен, как показано на рисунке 4.1(4) (Простой) путь между вершинами a и c включает ребра {a,b}, {b,c} и вершину c
Замечание: оба рисунка отражают одну и ту же ситуацию. С точки зрения графов в первую очередь имеет значение наличие связи между точками, а не ее геометрия.
2. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},
может быть изображен диаграммой, показанной на рис. 4.1.(5). Граф содержит два цикла {b, e, a}, {b, c, d}.
3. На рис. 4.1.(6)вершины а и с – смежные и е 1 , е 2 и е 3 - смежные ребра, вершины а и f смежными не являются, а е 2 и е 5 не являются смежными ребрами. Вершины b, с и d имеют степень 2, в то время как вершины a и f имеют степень 3.
Вернемся теперь к задаче Эйлера. При обходе графа возможны 2 ситуации: начало и конец пути совпадают, вход и выход различны. Для того, чтобы пройти соответствующим образом граф (обвести рисунок, не отрывая карандаш, не пропуская и не обводя дважды никакие ребра):
В первом случае все вершины должны иметь четные степени, во втором – четными должны быть все вершины, кроме входа и выхода.
Пример 4.1.(2)
Можно ли пройти граф на рис. 4.1(4), не пропуская и не проходя дважды никакие ребра?
Степени всех вершин четны, кроме вершин с и j со степью 3. Соответственно, единственный путь обхода – имеющий вершины c и j началом и концом (или наоборот)
Во многих случаях необходимы графы, у которых ребра, по существу, представляют собой улицу с односторонним движением. Это означает, что если рассматривается ребро, выходящее из вершины а в вершину b, то его нельзя рассматривать выходящим из вершины b в вершину а. Например, если граф моделирует поток нефти в трубопроводе, и если нефть течет из пункта а в пункт b, нам не хотелось бы, чтобы поток был и в обратном направлении, из пункта b в пункт а.
Определение 4.1(5)
Ориентированный граф или орграф G , который обозначается через G(V, Е) состоит из множества V вершин и множества Е упорядоченных пар элементов из У, называемого множеством ориентированных ребер или просто ребер, если понятно, что граф ориентирован. Элемент множества Е называется ориентированным ребром. Если , то а называется начальной вершиной ребра (а, b), b называется конечной вершиной.
Пример 4.1(3)
Орграф, у которого V = {а, b, с, d] и Е = {(а, b), (b, с), (с, с), (c, d), (d,b),(c,d),(d,a)} изображен на рис.
Определение 4.1.(6)
Рассмотрим несколько равносильных определений графа дерево.
1) Это связный граф, не имеющий циклов (о свойстве связности см 4.2.)
2) Граф, в котором любые 2 вершины соединены простым путем
3) Связный граф, теряющий связность при удалении любого ребра
4) Граф, в котором ребер на 1 меньше, чем вершин
Примеры деревьев:
Достаточно развитое генеалогическое дерево образует дерево. Если начать с конкретной (хорошо известной) личности и провести ребра между каждым из родителей и каждым сыном или дочерью, это сформирует дерево. При построении генеалогического дерева, однако, необходимо быть очень осторожным, чтобы браки между дальними родственниками не образовывали циклов.
Свойства графов
Теорема 4.2(1).
Сумма степеней вершин графа всегда четная.
Доказательство
Поскольку каждое ребро графа имеет два конца, степень каждого конца увеличивается на 1 за счет одного ребра. Таким образом, в сумму степеней всех вершин каждое ребро вносит 2 единицы, поэтому сумма должна в два раза превышать число ребер. Следовательно, сумма является четным числом.
Теорема 4.2.(2)
В любом графе количество вершин нечетной степени четно.
Доказательство
Доказательство проведем методом от противного: предположив, что теорема не верна, найдем противоречие, из которого будет следовать, что теорема справедлива. Если теорема не верна, то имеется нечетное количество вершин, степени которых нечетны. Но сумма степеней вершин с четными степенями четна. Сумма степеней всех вершин есть сумма степеней вершин с нечетными степенями плюс сумма степеней вершин с четными степенями. Поскольку сумма нечетного числа и четного числа есть число нечетное, сумма степеней всех вершин нечетная. Но это противоречит теореме 4.1(1), поэтому мы пришли к противоречию. Следовательно, делаем вывод, что теорема справедлива.
Пример 4.2.(1)
Можно ли организовать футбольный турнир между 7 командами так, чтобы каждая сыграла ровно по 3 матча?
Нет, так как, если мы составим граф с 7 вершинами, и попытаемся вывести по 3 ребра из каждой вершины. Согласно теореме 4.2(2), такой граф построить невозможно.
Определение 4.2(1).
Изоморфными называются графы одинаковой структуры. Два графа G и Н изоморфны (записывается или иногда G=H), если между их множествами вершин существует взаимно однозначное соответствие, сохраняющее смежность. Например, G и H на рис. 4. 2(2) изоморфны при соответствии .
Иначе говоря, вершины каждого из таких графов можно занумеровать так, что вершины можно занумеровать так, что вершины его соседние тогда и только тогда, когда они соседние во втором.
Заметим, что изоморфизм есть отношение эквивалентности на графах.
Определения 4.2(2)
Граф называется связным , если в нем между любыми двумя вершинами есть путь.
Компонента связности – часть графа, которая сама по себе связна, но ее нельзя расширить так, чтобы она осталась связной
Связностью x=x(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Из определения следует, что связность несвязного графа равна 0, а связность связного графа, имеющего точку сочленения, равна 1. Полный граф нельзя сделать несвязным, сколько бы вершин из него ни удалять.
