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

Если же на каждом ребре из множества Z={l1,lz} направление не задается, то граф G=(N,Z) называется неориентированным графом, или просто графом

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

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

В ориентированном графе для каждой вершины задаются входящие и исходящие ребра. Характеристиками отношений для вершины являются:

Степень захода din, равная числу ребер, входящих в вершину;

Степень исхода dout, равная числу ребер, исходящих из вершины.

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

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

Соответственно вводятся два показателя средней степени вершин

d̄in=∑i=1,gdin(ni)/g

d̄out=∑i=1,gdout(ni)/g

И два показателя вариации степени вершин

S2din=∑i=1,g(din(ni)- d̄in)2/g

S2dout=∑i=1,g(dout(ni)- d̄out)2/g

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

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

Δ=L/g(g-1)

4. Матричное представление графов

Пусть n – число акторов,

X – матрица размерности n*n,

где xij=1, если между акторами i и j есть связь, и xij=0, если между акторами i и j нет связи.

Матричное представление неориентированного графа

	n1	n2	n3	n4	n5	n6
n1	0	0	0	0	1	1
n2	0	0	1