Что такое изолированные вершины в графе

Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах

Ребро u , соединяющее вершину a с вершиной b ( a ≠ b ), назовём звеном, если множеству P принадлежать две инциденции: a, u, b и b, u, a .

Пример 1. Найти звенья в графе, представленном на рис А (под примером).

Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.

Иначе говорят также, что в описанном случае порядок двух концов ребра графа не существенен. В случае, когда порядок, в котором указаны вершины в инциденции, существенен, соответствующее ребро называет дугой.

Пример 2. Найти дуги в графе, представленном на рис А.

Ответ. Дуги данного графа представлены направленными линиями (стрелками), соединяющими первую из инцидентных вершин со второй. Вершины 1, 2, 9, 10 — дуги; первая из них соединяет вершину b с вершиной a , но не наоборот. То же самое относится и к другим дугам.

О дуге говорят, что она идёт из вершины b в вершину a .

Рёбра u , для которых имеются инциденции вида (a, u, a) , то есть вершина соединена сама с собой, называются петлями.

Пример 3. Найти петли в графе, представленном на всё том же рис А.

Ответ. В данном графе петли представлены линиями, начинающимися и заканчивающимися на одной и той же вершине. Линии 4 и 5 — петли.

Голой называют вершину, которая не инцидентна ни одному ребру графа.

Пример 4. Найти голую вершину в графе, представленном на всё том же рис А.

Ответ. В данном графе голой является вершина f .

Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.

Две вершины a и b называются смежными, если существует по крайней мере одно соединяющее их ребро. В частности, вершина смежна сама с собой в том и только в том случае, когда при ней имеется хотя бы одна петля.

Пример 5. В графе, представленном на рис А, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.

Ответ. В данном графе вершина c изолированная. Вершины a и b смежные, а вершины a и d — не смежные, вершина b смежна сама с собой.

Кратными называются рёбра, соединяющие одну и ту же пару вершин.

Пример 6. Найти кратные рёбра в графе, представленном на всё том же рис А.

Ответ. В данном графе рёбра 1, 2 и 3 — кратные; кратными являются также 4 и 5, рёбра 8, 9, рёбра 6, 7, а также 10 и 11.

Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.

Маршруты, цепи и циклы в графах

Маршрутом в графе называется последовательность вершин и рёбер (v 0 , e 1 , . e n , v n ) , такая, что любые две соседние вершины v i и v i+1 соединены ребром e i+1 . Если в маршруте v 0 = v n , то есть начальная вершина совпадает с конечной, то маршрут называется замкнутым или циклическим, в противном случае маршрут называется открытым. Число рёбер в маршруте называется длиной маршрута

Маршрут, в котором все рёбра различны, называется цепью.

Цепь, в которой все вершины, кроме, возможно, первой и последней, различны, называется простой цепью.

Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.

Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину), любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).

Ответ. В данном графе:

• например, a1b2a1b7d8c9c8d — маршрут из вершины a в вершину d длины 7;
• например, b5c6b7d — цепь;
• например, цепь a1b5c8d — простая, а цепь e3e4e — не простая;
• например, b5c9c8d7b — цикл длины 4 при вершине b;
• например, b5c8d7b — простой цикл длины 1 при вершине b.

Граф называется связным, если существует цепь между любыми двумя его вершинами.

Инцидентность

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).

• Автоморфизм — Изоморфизм графа с самим собой.

• Биграф — см. двудольный граф.
• Блок-дизайн с параметрами (v, k, λ) — покрытие с кратностью λ полного графа на v вершинах полными графами на k вершинах.

• Валентность вершины — см. Степень вершины
• Вершина, Узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G)
• Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
• Висячая вершина — вершина, степень которой равна 1 (то есть d(v) = 1 )
• Вполне несвязный граф (пустой граф, нуль-граф) — регулярный граф степени 0, то есть граф без рёбер.
• Вес ребра — значение, поставленное в соответствие данному ребрувзвешенного графа. Обычно вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра

• Гамильтонов граф — граф, в котором есть гамильтонов цикл.
• Гамильтонов путь — простой путь в графе, содержащий все вершины графа ровно по одному разу.
• Гамильтонов цикл — простой цикл в графе, содержащий все вершины графа ровно по одному разу.
• Геометрическая реализация — фигура, вершинам которой соответствуют вершины графа, рёбрам — рёбра графа и рёбра в фигуре соединяют вершины, соответствующие вершинам в графе.
• Геометрический граф — плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф.
• Гиперграф — совокупность из множества вершин и множества гиперрёбер (подмножество n-й евклидовой степени множества вершин, то есть гиперрёбра соединяют произвольное количество вершин).
• Гомеоморфные графы — графы, получаемые из одного графа с помощью последовательности подразбиений рёбер.
• Грань — область, ограниченная рёбрами в плоском графе, и не содержащая внутри себя вершин и рёбер графа. Внешняя часть плоскости тоже образует грань.
• Граф — базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножествомдекартова квадрата множества вершин (то есть каждое ребро соединяют ровно две вершины).
• Граф рода g — граф, который можно изобразить без пересечений на поверхности рода g и нельзя изобразить без пересечений ни на одной поверхности рода g-1.

• Двойственный граф. Граф А называется двойственным к планарному графу В, если вершины графа А соответствуют граням графа В, и две вершины графа A соединены ребром тогда и только тогда, когда соответствующие грани графа B имеют хотя бы одно общее ребро.
• Двудольный граф (или биграф, или чётный граф) — это граф G(V,E) , такой что множество вершин V разбито на два непересекающихся подмножества V₁ и V₂ , причём всякое ребро E инцидентно вершине из V₁ и вершине из V₂ (то есть соединяет вершину из V₁ с вершиной из V₂ ). То есть, правильная раскраска графа двумя цветами. Множества V₁ и V₂ называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из V₁ и V₂ являются смежными. Если , , то полный двудольный граф обозначается K_a,b .
• Дерево — связный граф, не содержащий циклов.
• Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины.
• Длинамаршрута — количество рёбер в маршруте (с повторениями). Если маршрут M = v₀,e₁,v₁,e₂,v₂. e_k,v_k , то длина M равна k (обозначается ).
• Длинапути — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v₁, v₂, …, v_n длина равна n-1.
• Дуга — это ориентированное ребро.
• Дополнение графа — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.

• Изолированная вершина — вершина, степень которой равна 0 (то есть нет ребер инцидентных ей).
• Изоморфизм. Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин).
• Интервальный граф — граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины инцидентны одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются.
• Инцидентность — понятие, используемое только в отношении ребра и вершины: если v₁,v₂ — вершины, а e = (v₁,v₂) — соединяющее их ребро, тогда вершина v₁ и ребро e инцидентны, вершина v₂ и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

• Клетка — регулярный граф наименьшего обхвата для заданной степени вершин.
• Клика — множество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом.
• Компонента связности графа — некоторое подмножествовершинграфа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
• Компонента сильной связности графа, слой — максимальное множество вершин ориентированного графа такое, что для любых двух вершин из этого множества существует путь как из первой во вторую, так и из второй в первую.
• Контур — замкнутыйпуть в орграфе.
• Коцикл — минимальный разрез, минимальное множество ребер, удаление которого делает граф несвязным.
• Кратные рёбра — несколько рёбер, инцидентных одной и той же паре вершин. Встречаются в мультиграфах.
• Кубический граф — регулярный граф степени 3, то есть граф в котором каждой вершине инцидентно ровно три ребра.

• Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья.

• Маршрут в графе — это чередующаяся последовательность вершин и рёбер v₀,e₁,v₁,e₂,v₂. e_k,v_k , в которой любые два соседних элемента инцидентны. Если v₀ = v_k , то маршрут замкнут, иначе открыт.
• Матрица достижимости орграфа — это матрица, содержащая информацию о существовании путей между вершинами в орграфе.
• Матрица инцидентности графа — это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.
• Матрица смежности графа — это матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обоим вершинам). Петля считается сразу двумя соединениями для вершины, то есть к значению элемента матрицы в таком случае следует прибавлять 2.
• Минимальный каркас (или Каркас минимального веса, Минимальное остовное дерево) графа — ациклическое множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нем минимальна.
• Множество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается Γ + (v)
• Мультиграф — граф, в котором существует пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.

• Направленный граф — то же что и ориентированный граф.
  • Направленный ациклический граф — ориентированный граф без контуров.
  • Обхват — длина наименьшего цикла в графе.
  • Окружение — длина наибольшего простого цикла в графе.
  • Орграф, ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведет от вершины v к вершине w, при этом вершина w смежная с вершиной v.
  • Остовом (неориентированного) связного графа G=(V,E) называется его частичный граф S=(V,T), являющийся деревом.
  • Остовный подграф — подграф, содержащий все вершины.
  • Петля — ребро, начало и конец которого находятся в одной и той же вершине.
  • Планарный граф — граф, который может быть изображён (уложен) на плоскости без пересечения рёбер. Изоморфен плоскому графу, то есть, является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от плоского графа изображением на плоскости . Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
  • Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным графом на плоскости.
  • Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству. (ср. Суграф.)
  • Полным графом называется граф, в котором для каждой пары вершин v₁,v₂ , существует ребро, инцидентное v₁ и инцидентное v₂ (каждая вершина соединена ребром с любой другой вершиной)
  • Полным двудольным называется двудольный граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
  • Полустепень захода в орграфе для вершины v — число дуг, входящих в вершину. Обозначается d + (v) .
  • Полустепень исхода в орграфе для вершины v — число дуг, исходящих из вершины. Обозначается d − (v) .
  • Правильная раскраска графа — раскраска, при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
  • Простая цепь — маршрут, в котором все вершины различны.
  • Простой граф — граф, в котором нет кратных рёбер и петель.
  • Простой путь — путь, все рёбра которого попарно различны. Другими словами, простой путь не проходит дважды через одно ребро.
    • Простой цикл — цикл, не проходящий дважды через одну вершину.
    — функция, заданная на вершинах ориентированного графа.
    • Размеченный граф — граф, для которого задано множество меток S, функция разметки вершин f : A → S и функция разметки дуг g : R → S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.
    • Разрез — множество ребер, удаление которого делает граф несвязным.
    • Раскраска графа — разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.
    • Ребро графа — базовое понятие. Ребро соединяет две вершины графа.
    • Регулярный граф — граф, степени всех вершин которого равны. Степень регулярности является инвариантом графа и обозначается r(G) . Для нерегулярных графов r(G) не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
      • Регулярный граф степени 0 (вполне несвязный граф, пустой граф, нуль-граф) — граф без рёбер.
      • Самодвойственный граф — граф, изоморфный своему двойственному графу.
      • Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
      • Связный граф — граф, в котором все вершины связаны.
      • Сечение графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
      • Сеть — в принципе, то же, что и граф, хотя сетями обычно называют графы, вершины которых определённым образом помечены.
      • Сильная связность. Две вершины в ориентированном графесильно связаны, если существует путь из первой во вторую и из второй в первую.
        • Сильно связный орграф — орграф, в котором все вершины сильно связаны.
        • Тождественный граф — граф, у которого возможен один единственный автоморфизм — тождественный. Образно говоря, тождественный граф — это «абсолютно несимметричный» граф.
        • Триангуляция поверхности — укладка графа на поверхность, разбивающая её на треугольные области; частный случай топологической триангуляции.
        • Тривиальный граф — граф, состоящий из одной вершины.
        • Турнир — ориентированный граф, в котором каждая пара вершин соединена одним ребром.
        • Узел — то же, что и Вершина.
        • Укладка: граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы рёбра графа при этом не пересекались. (См. Планарный граф, Плоский граф.)
        • Упорядоченный граф — граф, в котором рёбра, выходящие из каждой вершины, однозначно пронумерованы, начиная с 1. Рёбра считаются упорядоченными в порядке возрастания номеров. При графическом представлении часто рёбра считаются упорядоченными в порядке некоторого стандартного обхода (например, против часовой стрелки).
        • n-Фактор графа — регулярный остовный подграф степени n .
        • n-Факторизация графа — разбиение графа на независимые n-факторы.
        • Хроматическое число графа — минимальное количество цветов, требуемое для раскраски вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета.

        

        • Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи v₀,e₁. e_k,v_k вершины v₀ и v_k называются концами цепи. Цепь с концами u и vсоединяет вершины u и v. Цепь, соединяющая вершины u и v обозначается . Для орграфов цепь называется орцепью. В некоторых источниках простая цепь — цепь, рёбра которой различны, что является более слабым условием.
        • Цикл — замкнутая цепь. Для орграфов цикл называется контуром.
          • Цикл (простой цикл) в орграфе — это простой путьдлины не менее 1, который начинается и заканчивается в одной и той же вершине.
          • Цикл Гамильтона — то же, что и Гамильтонов цикл.
          • Частичный граф — то же, что и суграф.
          • Чётный граф — то же, что и двудольный граф.
          • Элементарный путь — путь, вершины которого, за исключением быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется циклом (элементарным циклом).
          • Элементарным стягиванием называется такая процедура: берем ребро (вместе с инцидентными ему вершинами, например, u и v) и «стягиваем» его, то есть удаляем ребро и отождествляем вершины u и v. Полученная при этом вершина инцидентна тем ребрам (отличным от), которым первоначально были инцидентны u или v.
          • Эйлеров граф — это граф, в котором существует цикл, содержащий все рёбра графа по одному разу (вершины могут повторяться).
          • Эйлерова цепь (или Эйлеров цикл) — это цепь (цикл), которая содержит все рёбра графа (вершины могут повторяться).

          Ссылки

          Литература

          • Харари Ф. Теория графов. — М .: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6

          Wikimedia Foundation . 2010 .

          Полезное

          Смотреть что такое «Инцидентность» в других словарях:

          инцидентность — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN incidence … Справочник технического переводчика

          ИНЦИДЕНТНОСТЬ — геометрический термин, употребляемый для обозначения отношения принадлежности (связи, соединения) между основными объектами геометрии: точками, прямыми, плоскостями. Свойства И. характеризуются так наз. аксиомами принадлежности (см., например,… … Математическая энциклопедия

          инцидентность — инцид ентность, и … Русский орфографический словарь

          ИНЦИДЕНТНОСТЬ — (от лат. incidens, род. падеж incidentis — случающийся), число вновь выявленных (новых) случаев возникновения инфекции за определённый период на 100, 1000, 10 тыс. или 100 тыс. животных, показатель частоты заболеваний и носительства; одна из … Ветеринарный энциклопедический словарь

          КОНФИГУРАЦИЯ — конечное множество точек, прямых, плоскостей, связанных между собой взаимными инцидентностями. К. могут быть как плоскими, так н пространственными. Плоская конфигурация конечная система рточек и gпрямых на плоскости, расположенных таким образом,… … Математическая энциклопедия

          Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия

          Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

          Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

          Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

          Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

          Что такое изолированные вершины в графе

          Графом называется пара , где — непустое конечное множество элементов, называемых вершинами , а — конечное семейство неупорядоченных пар элементов из (необязательно различных), называемых ребрами . Употребление слова «семейство» говорит о том, что допускаются кратные ребра. Будем называть множеством вершин » , а — семейством ребер графа . О каждом ребре вида и . Каждая петля саму с собой.

          При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; длины отрезков и расположение точек произвольны.

          Определение орграфа

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

          Полный граф

          Граф называется полным , если каждые две различные вершины его соединены одним и только одним ребром. В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Для задания полного графа достаточно знать число его вершин. Полный граф с вершинами обычно обозначается через и ребра, которые добавлены, тоже образуют граф. Такой граф называют дополнением графа и обозначают его .

          Дополнением графа называется граф с теми же вершинами, что и граф , и с теми и только теми ребрами, которые необходимо добавить к графу , чтобы получился полный граф.

          Является граф полным или нет, это его характеристика в целом.

          Полный ориентированный граф

          Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром. Если с каждого ребра полного ориентированного графа снять направление, то образуется полный граф с неориентированными ребрами.

          Рассмотрим соревнование, в котором каждая из команд играет с каждой из остальных команд по одному разу. Такое соревнование называют круговым турниром или турниром в один круг.

          Если каждая встреча непременно должна оканчиваться выигрышем одной из команд, то круговой турнир называют бескомпромиссным. Круговой бескомпромиссный турнир проводится, например, в волейболе и баскетболе.

          победила «.

          Двудольный граф

          Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества соединяет какую-нибудь вершину из называем двудольным графом . Такие графы иногда обозначаю простой, то он называется полным двудольным графом и обычно обозначается — число вершин соответственно в вершин и ребер.

          Степень вершины

          Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.

          Степенью вершины называется число ребер графа,которым принадлежит эта вершина. Вершина называется четной , если ее степень — число четное. Вершина называется нечетной , если ее степень — число нечетное. Две вершины графа называются смежными , если существует соединяющее их ребро, то есть ребро вида и называются инцидентными этому ребру , а ребро — инцидентным этим вершинам . Аналогично,два различных ребра графа называются смежными, если они имеют, по крайней мере, одну общую вершину. Иначе можно определить степень вершины. Степенью или валентностью вершины графа называется число ребер, инцидентных ; степень вершины будем обозначать через . При вычислении степени вершины будем учитывать петлю в два раза, а не один. Вершина степени называется изолированной вершиной , вершина степени называется висячей , или концевой , вершиной. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом .

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

          2. Число нечетных вершин любого графа четно.

          3. Во всяком графе с вершинами, где , всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

          4. Если в графе с вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени , либо в точности одна вершина степени .

          Связность графа

          Назовем граф связным ,если его нельзя представить в виде объединения двух графов, и несвязным — в противном случае.

          Маршрутом в данном графе называется конечная последовательность ребер вида

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

          Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень .

          Если — связный граф и степень каждой его вершины , тогда — простой цикл.

          Из каждой вершины данного графа в любую другую ведет путь. Начнем путь из какой-нибудь вершины е и пройдем по одному из двух ребер, которым принадлежит эта вершина. Попав во вторую вершину, выйдем из нее по второму ребру и так далее. С необходимостью все ребра графа будут пройдены, и мы вернемся в исходную вершину.

          Если граф — простой цикл, тогда степень каждой вершины равна двум.

          Так как граф — замкнутый простой путь, то из каждой его вершины можно попасть в любую другую, не проходя ни через одну вершину более одного раза. Степень каждой вершины такого графа равна двум.

          Покажем, что в простом цикле не может быть вершины, степень которой не равна двум.

          Если какая-то вершина в графе имеет степень меньше двух, то она не принадлежит никакому простому циклу.

          Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по определению) не может содержать все ребра, которым принадлежит эта вершина.

          Задачи, приводящие к графам

          Задача 1. Лист бумаги Плюшкин (Н.В.Гоголь «Мертвые души») разрезает на три части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листков он вновь разрезает на три более мелкие части и так далее. Сколько Плюшкин получает листиков бумаги, если разрезает листов?

          Решение. Будем считать листы бумаги вершинами графа. При разрезании одного листка на три части число листков увеличивается на два (появляются три новых вместо одного). Если же было разрезано листов, то образовалось листов.

          Задача 2. Утверждают, что в одной компании из пяти человек каждый знаком с двумя другими. Возможна ли такая компания?

          Решение. Каждого из этой компании будем считать вершиной графа. Двое знакомых соединим ребром. Из рассматриваемой компании нельзя выделить ни «четырехугольник», ни «треугольник», поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию. То есть схема знакомства единственная. Всякую схему, напоминающую многоугольник, принято называть циклом. Древние греки «цикл» называли «колесом».

          Задача 3. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.

          Решение. Переведем условие задачи на язык графов. Каждому из шахматистов поставим в соответствие вершину графа, соединим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим партию друг с другом. Получим граф с девятью вершинами. Степени его вершин равняются числу партий, сыгравших с соответствующими игроками. Покажем, что во всяком графе с девятью вершинами всегда найдутся хотя бы две вершины одинаковой степени.

          Каждая вершина графа с девятью вершинами может иметь степень, равную . Предположим, что существует граф , все вершины которого имеют разную степень, т.е. каждое из чисел последовательности является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина степени , то в нем не найдется вершина со степенью , так как эта вершина должна быть соединена ребрами со всеми остальными вершинами графа, в том числе с . Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени и . Следовательно, найдутся хотя бы две вершины, степени которых равны между собой. Таким образом, доказано, что в любой момент найдутся хотя бы двое, сыгравшие одинаковое число партий.

          Вывод. Во всяком графе с вершинами, где , всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

          Задача 4. Девять человек проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Нужно доказать, что либо в точности один участник еще не сыграл ни одной партии, либо в точности один сыграл все партии.

          Решение. Переведем условие задачи на язык графов. Пусть вершины графа — игроки, а каждое ребро означает, что соответствующие игроки уже сыграли между собой партию. Из условия известно, что в точности две вершины имеют одинаковые степени. Требуется доказать, что в таком графе всегда найдется либо только одна изолированная вершина, либо только одна вершина степени .

          В общем случае у графа с девятью вершинами степень каждой вершины может принимать одно из девяти значений: . Но у такого графа степени вершин принимают только восемь разных значений, ибо ровно две вершины имеют одинаковую степень. Следовательно, обязательно либо , либо будет значением степени одной из вершин.

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

          Допустим, что все же найдется граф с девятью вершинами, в котором ровно две вершины изолированные, а все остальные имеют разные степени. Тогда, если не рассматривать эти две изолированные вершины, останется граф с семью вершинами, степени которых не совпадут. Но такого графа не существует (см. задачу 3). Значит, это предположение неверно.

          Теперь допустим, что существует граф с девятью вершинами, в котором ровно две вершины имеют степень , а все остальные — несовпадающие степени. Тогда в дополнении данного графа ровно две вершины будут иметь степень , а остальные — попарно различные степени. Этого тоже не может быть (см. задачу 3), то есть и второе предположение неверно.

          Следовательно, у графа с девятью вершинами, из которых в точности две имеют одинаковую степень, всегда найдется либо одна изолированная вершина, либо одна вершина степени .

          Вернемся к задаче. Как и требовалось доказать, среди рассмотренных девяти игроков либо только один еще не сыграл ни одной партии, либо только один сыграл все партии. При решении этой задачи число можно заменить любым другим натуральным числом .

          Вывод. Если в графе с вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени , либо в точности одна вершина степени .

          Основные определения с примерами

          Граф – это некоторое конечное множество точек, называемых вершинами, и конечный набор линий, называемых ребрами, соединяющих некоторые пары точек из .

          Пример: схема автомобильных дорог, связывающих города некоторой области, является характерным примером графа.

          Ориентированный граф (орграф) – это граф, у которого пары в наборе X являются упорядоченными.

          Тогда – ориентированный граф.

          

          Дуга – это направленное ребро в орграфе.

          Пример: в приведенном выше примере для орграфа дугами являются ребра , , _.

          Начальная вершина – вершина орграфа, которой инцидентны только исходящие дуги.

          Пример: пусть – ориентированный граф, , , тогда – начальная вершина.

          

          Конечная вершина – вершина орграфа, которой инцидентны только заходящие дуги.

          Пример: пусть – ориентированный граф, , , тогда – конечная вершина.

          Петля – ребро графа, инцидентное единственной вершине.

          Пример: пусть – ориентированный граф, ,

          

          Изолированная вершина – вершина, которая не имеет инцидентных ребер.

          Пример: пусть – ориентированный граф, , , тогда , – изолированные вершины.

          Степень вершины – число инцидентных ребер, .

          Пример: пусть – граф, изображенный на рисунке. Тогда , , – соответственно степени вершин , , .

          

          Псевдограф – граф с кратными ребрами и петлями.

          Пример: пусть – ориентированный граф, , .

          Тогда – ориентированный псевдограф.

          

          Пустой граф – граф , в котором .

          Пример: пусть – граф, изображенный на рисунке. Он является пустым, т.к. ,

          

          Полный граф – граф , в котором любая пара вершин инцидентна единственному ребру. Обозначается , где , при этом .

          Пример: приведенный на рисунке граф является полным, т.к. это видно из определения и , при этом выполняется .

          

          Мультиграф – граф, в котором имеются кратные (параллельные) ребра.

          Мультиграф – это псевдограф без петель.

          Пример: пусть – ориентированный граф, , . Тогда – ориентированный мультиграф.

          

          Однородный граф – граф, все вершины которого имеют одну и ту же степень.

          Пример: следующие графы, приведенные на рисунке, являются однородными со степенью вершин . (рис. (а) и (б))

          Матрица смежности – квадратная матрица является матрицей смежности графа , если при в графе вершины и соединены ребрами, при вершины и в несмежны.

          Пример: для орграфа , изображенного на рисунке, приведем матрицу смежности:

          

          Матрица инцидентности орграфа – прямоугольная матрица , ,если вершина является началом дуги ; , если вершина является концом дуги ; , если вершина не инцидентна дуге .

          Пример: для орграфа, приведенного в примере для матрицы смежности, составим матрицу инцидентности:

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

          Пример: следующие графы, приведенные на рисунке, изоморфны:

          Маршрут длины H – чередующаяся последовательность вершин и ребер , обладающих тем свойством, что пара соседних элементов инцидентна.

          Пример: последовательность – маршрут длины 3, соединяющий вершины и в графе, приведенном на рисунке.

          Замкнутый маршрут – маршрут, у которого начальная вершина совпадает с конечной.

          Пример: пусть – граф, показанный на рисунке, тогда – замкнутый маршрут длины 4.

          

          Цепь – маршрут, в котором все ребра различны.

          Пример: пусть – ориентированный граф, приведенный на рисунке. Тогда – цепь из в длины 3.

          

          Простая цепь – цепь, в которой все вершины различны.

          Пример: для ориентированного графа , приведенного выше в примере с цепью, и – простые цепи из в длины 2.

          Цикл – цепь, у которой начальная и конечная вершина совпадают.

          Пример: пусть – граф, показанный на рисунке, тогда – цикл.

          Простой цикл – простая цепь, у которой концевые вершины совпадают.

          Пример: пусть – граф, показанный на рисунке, тогда – простой цикл.

          

          Эйлеров цикл – это цепь, содержащая все ребра графа в точности один раз, у которой начальная и конечная вершина совпадают.

          Пример: пусть – граф, показанный на рисунке, тогда существует Эйлеров цикл – .

          

          Гамильтонов цикл – это простая цепь, содержащая все вершины графа, у которой начальная и конечная вершины совпадают.

          Пример: приведенный на рисунке граф имеет Гамильтонов цикл: .

          Путь (ориентированная цепь) – цепь орграфа . в которой ориентация дуг (ребер) совпадает.

          Пример: для ориентированного графа, приведенного на рисунке, имеем путь из в длины 3: .

          

          Простой путь – путь, не содержащий повторяющихся вершин.

          Пример: для ориентированного графа, приведенного на рисунке, имеем простой путь из в : .

          

          Контур – путь, у которого начальная и конечная вершины совпадают.

          Пример: для ориентированного графа, приведенного на рисунке, имеем контур:

          

          Простой контур – контур, не содержащий повторяющихся вершин.

          Пример: для ориентированного графа, изображенного на

          

          рисунке, имеем простой контур: _.

          Подграф графа – граф , для которого и две вершины в смежны тогда и только тогда, когда они смежны в .

          Пример: пусть – исходный граф, показанный на рисунке (а), тогда – некоторый подграф графа (рисунок (б)).

          

          Суграф графа – граф содержит то же множество вершин, что и сам граф и .

          Пример: пусть – некоторый исходный граф, показанный на рисунке (а), тогда – некоторый суграф графа (б).

          

          Связный граф – граф, у которого любая пара вершин взаимодостижима.

          Пример: оба графа, которые были приведены выше в качестве примеров суграфа, являются также связанными графами.

          Сильносвязный граф – орграф, у которого любые две вершины взаимодостижимы.

          Пример: следующие два ориентированных графа, показанных на рисунке, являются сильносвязанными орграфами.

          Компонента связности графа – максимальный подграф графа , в котором все вершины попарно достижимы.

          Пример: у графа, показанного на рисунке, три компоненты связности.

          

          Сильная компонента орграфа – максимальный подграф орграфа , в котором любая пара вершин сильно связана.

          Пример: у орграфа, изображенного на рисунке, три компоненты сильной связности.

          

          Вершина ориентированного графа называется достижимой из вершины , если существует путь с началом в и концом в .

          Пример: в приведенном на рисунке орграфе вершина является достижимой из вершины .

          Минимальная длина простой цепи с началом в и концом в называется расстоянием между этими вершинами.

          Пример: в графе, изображенном на рисунке, расстояние между вершинами и равно трем.

          

          Смешанный граф – это граф, содержащий как дуги, так и ненаправленные ребра.

          Пример: граф, показанный на рисунке, является смешанным.

          

          Вершина инцидентна дуге тогда и только тогда, когда является либо началом, либо концом дуги .

          Пример: на рисунке вершины и инцидентны дуге .

          

          Отношение смежности:

          Две вершины смежны в графе тогда и только тогда, когда существует ребро графа, инцидентное им обоим. Два ребра смежны в графе тогда и только тогда, когда существует, по крайней мере, одна вершина, инцидентная им обоим.

          Пример: вершины и смежны, т.к. существует ребро x, инцидентное им обоим (рис (а)). Ребра и смежны, т.к. существует вершина , инцидентная им обоим (рис (б)).

          

          Обыкновенный граф – неориентированный граф, который не содержит параллельных ребер и петель; орграф, который не содержит строго параллельных дуг и петель.

          Пример: на рисунке изображен обыкновенный граф .

          

          Обозначим через k-ю степень матрицы смежности орграфа . Тогда элемент матрицы ориентированного псевдографа , где , равен числу всех путей длины из в .

          Пример: существует один путь из в длины 2.

          

          Граф называется деревом, если он является связным и не имеет циклов. Число ребер такого графа равно на единицу меньше числа его вершин.

          Пример: граф , изображенный на рисунке, является деревом. Из рисунка видно, что выполняется соотношение (в нашем случае).

          

          Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

          Похожие публикации:

          1. Как назначить администратора в рекламном кабинете вк
          2. Как отключить примагничивание в фотошопе
          3. Как удалить смс на iphone
          4. Компьютер и ноутбук как назвать одним словом