3.01.3. Обобщения понятия графа

Определение графа в п.1 предполагает, что любая пара вершин может быть соединена не более, чем одним ребром. Однако, существуют задачи и примеры графов, когда необходимо допускать существование нескольких ребер между одной и той же парой вершин. Такие ребра называются Кратными. Граф с кратными ребрами называется Мультиграфом. Графы, соответствующие исходному определению (в тех случаях, когда нужно подчеркнуть, что в них отсутствуют кратные ребра), называются Простыми графами. Кроме того, порой приходится рассматривать ребра вида {V, V}, соединяющие вершину V саму с собой. Такие ребра называются Петлями. Мультиграф с петлями называется Псевдографом.

Пара (V, E), где V -- непустое множество, а E Í V2 , называется Ориентированным графом (или кратко: Орграфом). Ребра такого графа представляют собой ориентированные (т. е. упорядоченные) пары вида (U, V). При этом, вершина U называется Началом ребра, а V -- Концом. Ориентированные ребра называются Дугами И изображаются в виде линий со стрелками, указывающими направление от начала ребра к концу.

Дуги (U, V) и (V, U), соединяющие одну и ту же пару вершин, но имеющие противоположные направления, называются Симметричными.

Можно рассматривать не только простые орграфы, но также ориентированные мульти - и псевдографы.

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

Как правило, при изучении тех или иных вопросов, заранее оговаривается (или ясно из контекста) о каких графах идет речь. В этом случае их просто называют графами без приставок "мульти-", "псевдо-" и т. д..

Если не оговорено противное, то везде далее "граф" будет означать "простой граф".

< Предыдущая		Следующая >