Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция № 11. Тема: графы и их способы задания

Тема: графы и их способы задания

Основные вопросы, рассматриваемые на лекции:

1. Виды графов

2. Степени вершин

3. Помеченные графы

4. Изоморфизмы графов

5. Матрицы смежности и инцидентности

Краткое содержание лекционного материала

1. Виды графов. Граф состоит из двух множеств. . Элементы множества называются вершинами, точками или узлами. . Неупорядоченные пары называются ребрами, линиями или дугами.

Если , то говорят, что ребро соединяет вершины и . При этом вершины u и v называются концами ребра .

Диаграмма графа G =(V, E) представляется в виде точек (или кружков) на плоскости, каждая из которых изображает вершину графа. Ребро графа изображается отрезком или дугой, соединяющей вершины u и v.

Диаграмму графа также называют графом.

 

Две вершины графа u и v называются смежными, если они соединены некоторым ребром e графа. Вершина u и ребро e называются инцидентными, если u является концом ребра e. Два ребра e и f графа называются смежными, если они инцидентны одной и той вершине u графа.

(p, q)- граф – это граф с p вершинами и q ребрами

(p ³1 и ).

Тривиальный (p,0)-граф не содержит ни одного ребра.

Полный граф – это -граф, содержащий все возможные ребра между вершинами.

Кроме графов (или неупорядоченных графов) рассматриваются и другие виды графов.

Мультиграф отличается от графа тем, что две вершины могут быть соединены двумя и более ребрами. При этом ребра, соединяющие две вершины в количестве двух и более, называются кратными.

Псевдограф отличается от графа тем, что в нем могут быть и кратные ребра, и петли (ребра, соединяющие вершины с самими собой).

2. Степени вершин. Степень вершины u – это число ребер, инцидентных вершине u. Вершина u называется изолированной (концевой), если ().

Следующая теорема была первой в истории теории графов (1936 г.)

Теорема 1 (Л.Эйлер). Сумма степеней всех вершин ()-графа равна удвоенному числу его ребер: .

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

Следствие. В графе число вершин с нечетными степенями четно.

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

.

3. Помеченные графы. Граф называется помеченным (или перенумерованным), если его точки обозначены попарно различными пометками.

Теорема 2. Существует помеченных графов с числом вершин n и помеченных (n, m)-графов.

Доказательство. Неупорядоченная пара { u, v } различных элементов u и v из множества V с числом элементов n есть сочетание без повторений из n элементов по 2. Поэтому число всех возможных ребер графа равно Cn 2.

Каждый граф имеет множество ребер – некоторое подмножество множества из Cn 2 элементов. Число всех подмножеств k -множества равно 2 k. Число всех -подмножеств k -множества равно .

4. Изоморфизмы графов. Графы G 1=(V 1, E 1) и G 2=(V 2, E 2) называются изоморфными, если существует биекция j: V 1® V 2, которая сохраняет отношение смежности между вершинами графа:

" u, v Î V 1 ({ u, vE 1Û{j(u),j(v)}Î E 2).

Пример изоморфных графов:

В этом примере биекция является изоморфизмом графов.

Графы G 1=(V 1, E 1) и G 2=(V 2, E 2) могут быть неизоморфными, если:

1) ;

2) ;

3) для каждого графы имеют различные числа вершин степени .

Графы могут быть неизоморфными, даже если все перечисленные три условия выполнены:

5. Матрицы смежности и инцидентности. Матрицей смежности графа называется матрица , определяемая следующим образом: для всех

Матрицы смежности представляют собой квадратные матрицы с элементами 0 и 1, у которых по главной диагонали расположены нули. Матрица смежности графа симметрична относительно главной диагонали.

Матрицей инцидентности -графа называется прямоугольная -матрица , определяемая следующим образом: для всех

<== предыдущая лекция | следующая лекция ==>
Лекция № 10. Тема: примеры рекуррентных соотношений | Лекция № 12
Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 792; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.