Здавалка
Главная | Обратная связь

Примеры неориентированных графов



Граф Вершины Ребра
Семья Люди Родственные связи
Город Перекрёстки Улицы
Сеть Компьютеры Кабели
Домино Костяшки Возможность
Дом Квартиры Соседство
Лабиринт Развилки и тупики Переходы
Метро Станции Пересадки
Листок в клеточку Клеточки Наличие общей границы

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

Например, три графа на рис. 11.1 совпадают, а два графа на рис. 11.2 — различны.

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

Ребро е и вершина v называются инцидентными друг другу, если вершина v является одним из концов ребра е.

Рис. 11.3. Псевдограф

Любому ребру инцидентно ровно две вершины, а вот вершине может быть инцидентно произвольное количество рёбер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет инцидентных ей рёбер (её степень равна 0).

Две вершины называются смежными, если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными, если они инцидентны одной вершине.

Путь в графе — это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в графе, изображённом на рис. 11.1, есть два различных пути из вершины a в вершину с: adbc и abc.

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

Граф называется связным, если все его вершины взаимно достижимы.

Длина пути — количество рёбер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc (см. рис. 11.1) — 3 и 2 соответственно.

Рис. 11.4. Несвязный граф

Расстояние между вершинами u и v — это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. 11.1 равно 2.

Цикл — это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис. 11.1.

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

Рис. 11.5. Граф Эйлера

Гамильтонов граф — это граф, в котором существует путь или цикл (без повторений), содержащий все вершины графа (см. рис. 11.5; искомый цикл: abdfca).







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.