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

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

Степень ni-ой вершины d(ni) - число ребер, инцидентных этой вершине.

Вершина степени 1 называется висячей.

Вершина степени 0 называется изолированной.

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

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

Средняя степень вершин d̄ для совокупности всех вершин графа равна:

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

Теорема 1. В графе G сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа.

d̄=2L/g

где L - общее число ребер графа;

g — общее число вершин графа.

Вариация средней степени вершин равна:

Sd2=∑i=1,g(d(ni) - d̄)2/g

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

Граф G называется полным, если любые две его вершины соединены ребром и он не содержит параллельных ребер.

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

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

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

Маршрутом между вершинами ni и nj в графе называется последовательность ребер, ведущая от вершины ni к вершине nj .

Длина маршрута - количество ребер в маршруте.

Путем называется маршрут, не содержащий циклов.

Циклом называется маршрут, начальная и конечная вершины которого совпадают.

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

Граф называется связным, если для любых двух его вершин существует маршрут, их соединяющий.

Если существуют вершины, для которых не существует соединяющего их маршрута, то граф называется несвязным.

Любой несвязный граф является совокупностью таких связных графов, которые обладают свойством: никакая вершина одного из них не связана маршрутом ни с какой вершиной другого. Каждый из этих графов называется компонентой графа .