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



Скачать 32.28 Kb.
Дата08.10.2012
Размер32.28 Kb.
ТипДокументы
Определение графа. Элементы графа.
Граф – множество V вершин и набор Е неупорядоченных или упорядоченных пар вершин; обозначается граф через G(V, E). Неупорядоченная пара вершин называется ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным. Граф, содержащий только дуги, – ориентированным. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра (дуги) называются кратными. Дуга (или ребро) может начинаться и кончаться в одной и той же вершине, такая дуга (ребро) называется петлей.

Далее под графом будем понимать граф без петель и кратных ребер; граф, в котором допускаются кратные ребра, назовем мультиграфом; а граф, в котором допускаются кратные ребра и петли – псевдографом.

Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. Две вершины соединяются непрерывной линией тогда и только тогда, когда в графе G есть ребро с этими вершинами. Ребра графа будем обозначать парами точек, например, , а также малыми латинскими буквами (см. рис.1)



Вершины, соединенные ребром или дугой, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро (дуга) и любая из его двух вершин называются инцидентными. Говорят, что ребро соединяет вершины А и В, а дуга начинается в вершине А и кончается в вершине В. Вершина, не принадлежащая ни одному ребру, называется изолированной. Граф, состоящий только из изолированных вершин, называется нуль-графом. Граф называется полным, если любые две его различные вершины соединены одним и только одним ребром (рис.1, в)).

Любой неполный граф можно дополнить до полного (рис. 2.)





Дополнением графа называется граф с теми же вершинами, что и граф , и с теми и только теми ребрами, которые нужно добавить к графу , чтобы он стал полным (рис.2, б)).
Пример 3.1. Выяснить, сколько ребер в полном графе с 5 вершинами.
Решение.

Изобразим полный граф с 5 вершинами (рис. 3).


В данном графе 10 ребер: (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5).

Число ребер графа, которым принадлежит вершина А, будем обозначать и называть степенью вершины А. Вершина А называется четной, если - четное число, и нечетной, если - нечетное число.
Теорема 3.1. В графе сумма степеней всех его вершин есть число четное, равное удвоенному числу ребер графа.

Следствие. Число нечетных вершин графа четно.
Теорема 3.2. Во всем графе с n вершинами, где , всегда найдутся по крайней мере две вершины с одинаковыми степенями.
Теорема 3.3. Если в графе с n вершинами, где , в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени .
Граф называется однородным степени n, если степень любой его вершины равна n.
Пример 3.2. Существует ли полный граф с 7 ребрами?
Решение.

Пусть у графа G имеется n вершин. Тогда степень каждой вершины равна (т.к. граф полный). По условию в графе 7 ребер. По теореме 4.1. сумма степеней всех вершин равна . С другой стороны, сумма степеней всех вершин графа равна . Тогда получаем уравнение: . Отсюда . Решая его, получим , , , отсюда следует, что полного графа с 7 ребрами не существует.



Пример 3.3. 7 студентов, разъезжаясь на каникулы, договорились, что каждый из них пошлет письма трем остальным. Может ли оказаться, что каждый получит письма от тех друзей, которым пишет сам?

Решение.

Имеем граф с 7 вершинами, степень которых равна 3. Получаем следующую математическую интерпретацию данной задачи: существует ли неполный однородный граф с 7 вершинами степени 3? Сумма степеней вершин данного графа равна - нечетное число. Получаем противоречие теореме 4.1, которая утверждает, что сумма степеней вершин графа есть число четное.

Ответ: не может.

Похожие:

Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным icon1. Основные понятия и определения
Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром, если упорядочена – дугой. Граф, состоящий только из...
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconГраф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер
Вершина и ребро называются инцидентными, если вершина является одним из концов ребра. Степень вершины – это число ребер, инцидентных...
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconТеория графов и её применение
Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью...
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconКомплексные числа § Алгебраическая форма
Определение Комплéксным1 числом называется упорядоченная пара действитель­ных чисел (a, b), a, b R
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconОпределение. Вектором называется направленный отрезок (упорядоченная пара точек). К векторам относится также и нулевой
Определение. Длиной (модулем) вектора называется расстояние между началом и концом вектора
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconОпределение. Вектором называется направленный отрезок (упорядоченная пара точек). К векторам относится также и нулевой
Определение. Длиной (модулем) вектора называется расстояние между началом и концом вектора
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным icon10 билет Полный подграф Полный граф
Полный граф – граф, каждая вершина которого соединена ребром с остальными. Все вершины смежны
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconЗанятие 6: Правильные раскраски графов
Раскраска вершин графа правильная, если концы каждого ребра – разного цвета. Граф называется k-раскрашиваемым, если его можно правильно...
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconЛекция №1 (06. 09. 11) Глава Векторная алгебра § Векторы на плоскости и в пространстве
Определение Направленным отрезком называется упорядоченная пара точек (на плоскости или в трёхмерном пространстве)
Ребром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным iconПлоские графы и теорема Рамсея
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org