Матрица инцидентности

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

в случае, если связь j «выходит» из вершины i,

−1,

если связь «входит» в вершину,

во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким (размер пропорционален |V||E|) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).

Особенности данного представления[]

· Используется для любых графов, даже если есть петля.

· В каждом столбце обязательно должны стоять две единицы (либо 1 и -1 в случае ориентированного графа).

2)

Список рёбер

Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру.

Размер занимаемой памяти:

Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.

43. Эйлеровы графы (1). Гамильтоновы цепи и циклы (2). Гамильтоновы графы (3).

1)

2 и 3)

44. Ациклический граф. Лес. Деревья. Свойства деревьев (1). Корневые деревья. Высота ордерева. (2)

45. Остовное дерево графа (1). Минимальные остовы графов (2).

1)

2)

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

Date: 2015-12-13; view: 438; Нарушение авторских прав