Цикл в графе это

Цикл в графе это

Маршрут на графе G = (V, Е) из вершины и, в вершину ип это конечная последовательность вершин W = uv и2, . ип таких, что (мр uj+2) с E(G) для каждого /, 1

Виды вершин и рёбер графа

Ребро u , соединяющее вершину a с вершиной b ( ab ), назовём звеном, если множеству 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 .

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

Читайте также:  Обзор графических планшетов wacom

Две вершины 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 = v n , то есть начальная вершина совпадает с конечной, то маршрут называется замкнутым или циклическим, в противном случае маршрут называется открытым. Число рёбер в маршруте называется длиной маршрута

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

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

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

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

Читайте также:  Светодиодные лампы general отзывы

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

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

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

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

Определение 2. Путь от xi до xj называется простым, если он не проходит через одну вершину более одного раза.

Пример 1. Рассмотрим граф

В данном графе есть следующие пути от x1 до x6:

Первые три пути являются простыми.

Определение 3. Циклом называется путь, в котором начальная и конечная вершины совпадают. Длиной цикла называется число ребер в этом цикле.

Определение 4. Цикл называется простым, если он не проходит через одну вершину более одного раза.

Пример 2.Рассмотрим граф

В данном графе есть следующие циклы:

Первые три цикла являются простыми.

Теорема.Если у графа G(X,T) все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

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

Читайте также:  Программа по планировке и дизайну квартиры

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете. 8771 — | 7581 — или читать все.

Ссылка на основную публикацию
Футбольный менеджер без интернета
Да, уже четыре года назад Испания выиграла Евро 2012. С того времени много воды утекло и теперь у других команд...
Форд экоспорт белый фото
Компания Форд славится тем, что каждое обновление их машин несет в себе кучу перемен. Не стал исключением и недорогой городской...
Форм факторы корпусов пк размеры
Главная FAQ Железо Типы компьютерных корпусов Типы компьютерных корпусов Говоря слово "компьютер" многие подразумевают системный блок компьютера, и в принципе...
Футбольный менеджер с реальными командами
Бесплатная онлайн игра. Только в нашем футбольном менеджере игры проходят в реальном времени и можно менять тактику непосредственно во время...
Adblock detector