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

Пример. Определение.Если элементами множества E являются упорядоченные пары, то граф называется ориентированным (или орграфом)

Определение. Если элементами множества E являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества E – дугами. На диаграмме дуги изображаются стрелками.

Пример. V = { }, E = { = { }, = { }, = { }, = { }, = { }},

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

Определение. Если E не множество, а семейство, то есть если E содержит одинаковые элементы, то такие элементы называются кратными рёбрами, а граф называется мультиграфом.

33. Степень вершины. Лемма Эйлера. Теорема о числе вершин нечетной степени

Определение. Пусть - вершины, 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, называется полустепенью исхода , а входящих – полустепенью захода .

Лемма (Эйлера). Сумма степеней вершин графа равна удвоенному количеству рёбер

, .

Доказательство. При подсчёте суммы степеней вершин каждое ребро учитывается два раза.

Теорема о числе вершин нечётной степени. Число вершин нечётной степени в графе чётно.

Доказательство. В противном случае сумма степеней вершин была бы нечётной, что противоречит лемме Эйлера.

34. Смежность вершин и ребер графа. Матрица смежности.

Определение. Пусть - вершины, 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, называется полустепенью исхода , а входящих – полустепенью захода .

Рассмотрим граф G(V,E) с p вершинами и q рёбрами.

1. Матрица смежности. Так называется матрица M: p x p,

Это определение подходит и для орграфа D(V,E).

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