Ориентированные графы

Подграфы

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

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

Примеры подграфов:

V₂ V₁ V₁

V₅ V₅

V₃ V₄ V₄

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

Граф	Вершины	Ребра
Семья	Люди	Родственные связи
Сеть	Компьютер	Линии связи

Дуга – упорядоченная пара вершин (изображается направленной линией).

Входящая степень вершины – количество входящих в вершину дуг. Исходящая степень вершины – количество исходящих из вершин дуг.

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

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

Орграф может быть использован в качестве семантической сети.

Дата добавления: 2014-01-20