АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Пример. Приведём основные свойст

G: D:

Приведём основные свойства матрицы смежности

1) Матрица смежности неориентированного графа симметрична .

2) Сумма элементов матрицы M(G) по i-ой строке (по i- му столбцу) равна степени i-й вершины:

3) Суммы элементов матрицы M(D) по i-й строке и по i-му столбцу соответственно равны полустепени исхода и полустепени захода i-ой вершины

.

35. Инцидентность вершин и ребер графа. Матрица инцидентности

Определение. Пусть - вершины, e = () – соединяющие их ребро. Тогда вершина и ребро e инцидентны, вершина и ребро e также инцидентны. Два ребра, инцидентные одной вершине, называются смежными, две вершины, инцидентные одному ребру, также называются смежными.

Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается Г(v): Г(v) = {u V: (u,v) E}. Если A V – множество вершин, то Г(A) – множество всех вершин, смежных с вершинами из A: Г(A) = Г(v).

Пример. В этом графе вершины и , и , и , и , и смежные, а вершины и не смежные. Рёбра и , и , и , и , и , и , и , и смежные, и , и не смежные.

Определение. Количество рёбер, инцидентных вершине v, называется степенью (или валентностью) вершины v и обозначается d(v).

Определение. Если степень вершины равна 0, то вершина называется изолированной. Если степень вершины равна 1, то вершина называется висячей.

Определение. Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода , а входящих – полустепенью захода .

Матрица инциденций. Так называется матрица H: p x q,

для неориентированного графа:

для ориентированного графа:

Пример.

Приведём основные свойства матрицы инцидентности

1) Сумма строк матрицы H(D) является нулевой строкой.

2) Сумма строк матрицы по модулю 2 H(G) является нулевой строкой

36. Типы графов: пустой, полный, регулярный, двудольный

Определение. Граф G(V,E) называется пустым, если E = .

Определение. Граф G(V,E) называется полным, если в нём любые две вершины смежные, то есть . Полный граф определяется числом своих вершин и обозначается , где n = |V|. Полный граф имеет максимально возможное число рёбер: q()=p(p-1)/2.

Определение. Если степени всех вершин равны k, то граф называется регулярным степени k.

Определение. Граф G(V,E) называется двудольным, если множество V можно разбить на два непересекающихся подмножества и : , таким образом, что любое ребро из E соединяет вершину из с вершиной из . Множества и называются долями двудольного графа. Если двудольный граф содержит все возможные рёбра, то есть , то он называется полным двудольным графом и обозначается , где m=| |, n=| |.

Дата добавления: 2015-09-27 | Просмотры: 575 | Нарушение авторских прав