Основные объекты графов

Данный курс был прочитан для студентов второго курса факультета "К" групп К2-221, 222, 224, 281, 331 и 361 в весеннем семестре 2005/2006 учебного курса доц. Каф. Кибернетики Порешиным П.П.

Появление этого конспекта на сайте кафедры для студентов стало возможным благодаря инициативе студента группы К2-331 Шутяева Александра, который тщательно их записал с последующей обработкой текста в текстовом, графическом и формульном редакторах.

Основные объекты графов

- носитель метаграфа (конечное множество вершин). . - сигнатура метаграфа (конечное множество связей между вершинами). .

Граф, орграф и гиперграф отличаются друг от друга свойствами сигнатуры.

Для графа: - множество ребер, связывающих две вершины.
.

Для орграфа (ориентированный граф): - множество дуг.
.

Для гиперграфа (мограф – модельный граф): - множество граней.
. Грань – подмножество вершин мографа.

Примеры

Граф:
Орграф:

Гиперграф:

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

Все введенные ранее графы можно было бы разделить на три категории.

некоторые множества