Лекция 5 Теория графов, сетей, социальные сети и институты

Несвязный граф. Неориентированные графы.

Теория графов. Неориентированные графы.

Ребро a называется мостом графа G, если граф, получившийся из G после удаления ребра a (обозначается G\a), содержит больше компонент, чем граф G.

Ребро a графа G является мостом тогда и только тогда, когда a не принадлежит ни одному циклу. 

Теория графов. Неориентированные графы.

Коэффициент плотности графа D — является отношением числа ребер в графе к числу ребер в полном графе с тем же числом вершин:

Δ=2L/g(g-1)=d̄/(g-1)

Коэффициент плотности изменяется от 0 до 1. Единичная плотность соответствует полному графу, нулевая — графу, в котором все вершины изолированные.

Если отсутствуют петли и параллельные ребра

Теория графов. Неориентированные графы.

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

Коэффициент плотности подграфа, равен

Δs=2Ls/gs(gs-1)

Δs — число ребер подграфа;

 gs— число вершин подграфа.

Теория графов. Неориентированные графы.

Теория графов. Неориентированные графы.

Деревья - частный случай графов, содержат минимальное количество ребер, необходимое для связности.

У деревьев:

• любое ребро представляет собой мост;
• L=g-1;
• существует только один путь между любыми двумя вершинами.

С помощью деревьев представляются возможные действия игроков: дерево игры.

Теория графов. Неориентированные графы.

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

Если рассматривается множество упорядоченных пар lk=(ni,nj) из множества точек N={n1,ng} и на каждом ребре из множества Z={l1,lz} задается направление, то граф Gd=(N,Z) называется ориентированным графом.