определениями графа и его элементов;
с операциями над графами;
с деревьями,
лесом, бинарными деревьями;со способами задания графа, с изоморфными графами.
- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Основные понятия и определения графов и его элементов
Содержание
- 2. Цель лекции – познакомить студентов:с основными понятиями
- 3. 2.1. Основные понятия и определения графа и
- 4. Две вершины графа называются смежными, если существует
- 5. Если граф G имеет ребро , у
- 6. Два ребра называются смежными, если они имеют
- 7. Рёбра, которые начинаются в одной и той
- 8. На рисунке кратными являются, например, рёбра х1(А,
- 9. На рисунке вершина А имеет степень, равную
- 10. E Вершина графа, имеющая степень, равную нулю, называется
- 11. На рисунке вершины А, В, Е, G, H – висячие. х1х2х3х4х5х6х7СDFABEHG
- 12. Теорема 3.1. В графе
- 13. Вершина называется чётной (нечётной), если её степень
- 14. Теорема 3.2. Число нечётных вершин любого графа
- 15. Дополнением графа называется граф
- 16. Если все пары во множестве X являются
- 17. Началом ребра называется вершина, указанная в кортеже
- 18. Степень входа вершины V обозначается deg+(V), а
- 19. Последовательность попарно смежных вершин неориентированного графа, т.е.
- 20. На рисунке HCDFD – маршрут длиной 4.
- 21. В графе на рисунке (t, s, p,
- 22. Расстоянием между двумя вершинами называется минимальная длина
- 23. В графе на рисунке (t, s, p) – 3-цепь.
- 24. В орграфе маршрут является ориентированным и называется
- 25. На рисунке (u, s, r, t) –
- 26. Неориентированный граф называется связным, если между любыми
- 27. Две вершины называются связными, если существует маршрут
- 28. Ребро связного графа G называется мостом, если
- 29. Графы называются изоморфными, если существует взаимно-однозначное соответствие
- 30. Граф G называется планарным (плоским), если существует
- 31. Областью называется подмножество плоскости, пересекающееся с планарным
- 32. Множество А3 на рисунке областью не является,
- 33. АТеорема 2.5 (Эйлера). Связный плоский граф с
- 34. Решение. Предположим, что эти 9 тропинок можно
- 35. Каждая из пяти граней имеет по крайней
- 36. Граф называется двудольным, если его вершины разбиты
- 37. Эйлеровым путём (циклом) графа называется путь (цикл),
- 38. Гамильтоновым путём (циклом) графа G называется путь
- 39. Задача 17 «О кёнигсбергских мостах» (Эйлера). Необходимо
- 40. Решение.Представим задачу в виде графа, в котором
- 41. Но в теореме 3.6. говорится о том,
- 42. 2.2. Операции над графамиОбъединением графов
- 43. х3х4х6G1V2V1V3V4V5х3х1х5G=G1UG2х6х4х4х3V3V2V1G=G1∩G2х2х2V2V1V3V4х7V5х1G=G1 G2V4х7х5х6
- 44. Подграфом графа называется граф
- 45. Несвязный граф G состоит из двух компонент связности, т.е. из двух подграфов и .
- 46. 2.3. Деревья. Лес. Бинарные деревьяДеревом называют конечный
- 47. Для каждой пары вершин дерева – узлов
- 48. граф связен и имеет п – 1
- 49. Упорядоченное объединение деревьев представляет собой несвязный граф,
- 50. При описании деревьев принято использовать термины: отец,
- 51. V3 V5 V1 Для упорядоченных деревьев принята
- 52. Деревья, в которых каждый узел либо является
- 53. V1 V10V7 V15V9V0 V2 V4 V13V3 V5 Бинарное деревоV6 V8 V14V11V12V16V11
- 54. Цикломатическое число графа Цикломатическим числом неориентированного графа
- 55. 3.4. Способы задания графа. Изоморфные графы Геометрическое
- 56. Матрицей инцидентности называется таблица В, состоящая из
- 57. Матрицей смежности графа без кратных рёбер называется
- 58. Задача. Пусть граф G задан матрицей смежности
- 59. Скачать презентацию
- 60. Похожие презентации
Цель лекции – познакомить студентов:с основными понятиями и определениями графа и его элементов;с операциями над графами;с деревьями, лесом, бинарными деревьями;со способами задания графа, с изоморфными графами.
Слайд 2
Цель лекции – познакомить студентов:
с основными понятиями и
определениями графа и его элементов;
лесом, бинарными деревьями;со способами задания графа, с изоморфными графами.
Слайд 3 2.1. Основные понятия и определения графа и его
элементов
Графом называется пара двух конечных множеств: множество
точек и множество линий, соединяющих некоторые пары точек.Точки называются вершинами, или узлами, графа, линии – рёбрами графа.
Если ребро графа G соединяет две его вершины V и W, (т.е. ), то говорят, что это ребро им инцидентно.
Слайд 4 Две вершины графа называются смежными, если существует инцидентное
им ребро: на рисунке смежными являются вершины А и
В, А и С.Слайд 5 Если граф G имеет ребро , у которого
начало и конец совпадают, то это ребро называется петлёй.
На рисунке ребро q(С, С) – петля.С
A
B
D
E
q
Слайд 6 Два ребра называются смежными, если они имеют общую
вершину. На рисунке смежными являются, например, рёбра х1 и
х2 с общей вершиной С.х1
х2
х3
х4
х5
х6
х7
С
D
F
A
B
E
H
G
Слайд 7 Рёбра, которые начинаются в одной и той же
вершине, заканчиваются также в одной и той же вершине,
называются кратными, или параллельными. Количество одинаковых пар вида называется кратностью ребра . Число рёбер, инцидентных вершине А, называется степенью этой вершины и обозначается (от англ. degree – степень).
Слайд 8 На рисунке кратными являются, например, рёбра х1(А, В),
х2(А, В). Вершинам А и С инцидентны рёбра х3,
х4, х5. Следовательно, ребро АС имеет кратность, равную 3, а ребро АВ – кратность, равную 2.А
С
В
х1
х2
х5
х3
х4
Слайд 9 На рисунке вершина А имеет степень, равную 1,
вершина С – 4, вершина D – 2. Записывается
это в виде: deg(A)=1, deg(C)=4, deg(D)=2.х1
х2
х3
х4
х5
х6
х7
С
D
F
A
B
E
H
G
Слайд 10
E
Вершина графа, имеющая степень, равную нулю, называется изолированной.
Граф, состоящий из изолированных вершин, называется нуль-графом. Вершина графа,
имеющая степень, равную 1, называется висячей.На рисунке вершина
Е – изолированная:
deg(E)=0.
A
B
D
C
Слайд 12
Теорема 3.1. В графе сумма
степеней всех его вершин – число чётное, равное удвоенному
числу рёбер графа:где - число вершин;
- число рёбер графа.
Слайд 13 Вершина называется чётной (нечётной), если её степень –
чётное (нечётное) число.
На рисунке deg(D)=2, deg(F)=3, значит у
графа вершина D является чётной, а F – нечётной.х1
х2
х3
х4
х5
х6
х7
С
D
F
A
B
E
H
G
Слайд 14 Теорема 3.2. Число нечётных вершин любого графа –
чётно.
Следствие. Невозможно начертить граф с нечётным числом нечётных вершин.
Граф
G называется полным,если любые две его различные
вершины соединены одним и
только одним ребром.
Слайд 15 Дополнением графа называется граф с
теми же вершинами V, что и граф G, и
имеющий те и только те рёбра , которые необходимо добавить к графу G, чтобы он стал полным. На рисунке дополнением графа G1 до графа G является графG
G1
Слайд 16 Если все пары во множестве X являются упорядоченными,
т.е. кортежами длины 2, то граф называется ориентированным, орграфом,
или направленным.
Слайд 17 Началом ребра называется вершина, указанная в кортеже первой,
концом – вторая вершина этой пары (графически она указана
стрелкой). Рёбра ориентированного графа имеют определённые фиксированные начало и конец и называются дугами.Степенью входа (выхода) вершины ориентированного графа называется число рёбер, для которых эта вершина является концом (началом).
Дуги орграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. одинаковые направления.
Слайд 18 Степень входа вершины V обозначается deg+(V), а степень
выхода – deg-(V). На рисунке deg+(V1)=1, deg+(V2)=1, deg+(V3)=2, deg-(V1)=1,
deg-(V2)=2, deg-(V3)=1.Кратными являются дуги t(V2, V3) и u(V2, V3).
V1
V2
V3
t
r
s
u
Слайд 19 Последовательность попарно смежных вершин неориентированного графа, т.е. последовательность
рёбер неориентированного графа, в которой вторая вершина предыдущего ребра
совпадает с первой вершиной следующего, называется маршрутом.Число рёбер маршрута называется длиной маршрута.
Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом.
Слайд 20 На рисунке HCDFD – маршрут длиной 4. Обозначение:
|HCDFD|=4. Маршрут принято задавать как последовательность рёбер, поскольку это
удобно при наличии кратных рёбер.х1
х2
х3
х4
х5
х6
х7
С
D
F
A
B
E
H
G
Слайд 21 В графе на рисунке (t, s, p, r),
(u, s, t, r) – циклы длиной 4, (r,
t, q, s, u) – цикл длиной 5, (t, s, u, r, t, s, p, r) – 8-цикл, (p, u) – 2-цикл, петля (q) – 1-цикл.s
Слайд 22 Расстоянием между двумя вершинами называется минимальная длина из
длин всех возможных маршрутов между этими вершинами при условии,
что существует хотя бы один такой маршрут. Обозначается как (от лат. distantio – расстояние) .Если любое ребро в маршруте встречается только один раз, то маршрут называется цепью.
Слайд 24
В орграфе маршрут является ориентированным и называется путём.
Путь
– упорядоченная последовательность рёбер ориентированного графа, в которой конец
предыдущего ребра совпадает с началом следующего и все рёбра единственны.Цикл в орграфе – путь, у которого совпадают начало и конец.
Цепь, путь и цикл в графе называются простыми, если они проходят через любую из вершин не более одного раза.
Слайд 25 На рисунке (u, s, r, t) – 4-путь,
(r, u) – 2-путь, (s, r, t, s) путём
не является.(s,r,t) и (u, s, r) – 3-циклы.
V1
V2
V3
t
r
s
u
Слайд 26 Неориентированный граф называется связным, если между любыми двумя
его вершинами есть маршрут.
Графы G1 и G3 на
рисунке являются связными, а граф G2 – несвязным.G1
G2
G3
Слайд 27 Две вершины называются связными, если существует маршрут между
ними. Связность между вершинами является отношением эквивалентности.
Все подграфы Vi
(классы эквивалентности) графа G называют связными компонентами, или компонентами связности.Теорема 2.3. Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая его вершина имела степень, равную 2.
Слайд 28 Ребро связного графа G называется мостом, если после
его удаления G станет несвязным и распадётся на два
связных графа и .Теорема 2.4. Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.
На рисунке мост (СЕ) разделил связный граф
На два различных связных графа: с вершинами (А,В,С,D)
и с вершинами
(E,F,G,H,I). Ребро ВС –
мост.
E
Слайд 29 Графы называются изоморфными, если существует взаимно-однозначное соответствие между
их рёбрами и вершинами, причём соответствующие рёбра соединяют соответствующие
вершины.D
B
A
C
1
2
3
4
Слайд 30 Граф G называется планарным (плоским), если существует изоморфный
ему граф , в изображении которого на плоскости рёбра
пересекаются только в вершинах. Графы G1 и G3 являются планарными, а G2 – нет.G1
G2
G3
Слайд 31 Областью называется подмножество плоскости, пересекающееся с планарным графом
только по некоторому простому циклу графа, являющемуся границей области.
Данный
граф выделяетв плоскости следующие
области: А1 с границей q;
А2 с границей (o,s,t); A3 c
границей (q,s,u,r,t); A4 c
границей (p,u); А5 с гра-
ницей (o,p,r).
s
А3
A1
C
t
p
u
q
r
А4
А5
А2
о
Слайд 32 Множество А3 на рисунке областью не является, так
как пересечение А3∩G содержит точку Q, не принадлежащую никакому
циклу.C
G
Слайд 33
А
Теорема 2.5 (Эйлера). Связный плоский граф с n
вершинами и m рёбрами разбивает плоскость на r областей
(включая внешнюю), причём .Задача 16 «О трёх колодцах». Проложить дорожки от трёх домов к каждому из трёх колодцев так, чтобы никакие две дорожки не пересекались.
К1
В
С
К2
К3
Слайд 34
Решение.
Предположим, что эти 9 тропинок можно проложить.
Обозначим
домики точками А, В, С, колодцы - точками К1,
К2, К3. Каждую точку-дом соединим с каждой точкой-колодцем.Получились ребра (графа) в количестве девяти штук, которые попарно не пересекаются.
Такие ребра образуют на рассматриваемой плоскости задачи многоугольник, поделенный на меньшие многоугольники.
Для такого разбиения должно выполняться известное соотношение Эйлера п - т + r = 2, причем n = 6 и m = 9. Получается, r = 5.
Слайд 35 Каждая из пяти граней имеет по крайней мере
четыре ребра, так как, по условию задачи Эйлера, ни
одна из дорожек не должна напрямую соединять два колодца или два дома.Так как любое ребро лежит ровно в 2-х гранях, то количество ребер графа должно быть не меньше 5*4/2 = 10.
Это противоречит условию исходной задачи, по которому их число равно девять!
Полученное противоречие доказывает, что ответ в задаче о 3х колодцах Эйлера отрицателен.
Слайд 36 Граф называется двудольным, если его вершины разбиты на
два непересекающихся подмножества: , а рёбра связывают
вершины только из разных классов (не обязательно все пары).Если каждая вершина множества V1 связана ребром с каждой вершиной множества V2, то двудольный граф называется полным двудольным и обозначается , где .
Примером двудольного полного графа является граф к рассмотренной задаче, которую называют «Три дома – три колодца», показывая этим два непересекающихся множества вершин графа.
Слайд 37 Эйлеровым путём (циклом) графа называется путь (цикл), который
содержит все рёбра графа только один раз. Граф, обладающий
эйлеровым циклом, называется эйлеровым. Плоский эйлеров граф также называют уникурсальным.Теорема 3.6. Граф G является эйлеровым тогда и только тогда, когда G – связный граф, имеющий все чётные вершины.
На рисунке изображён
пример эйлерова графа.
Слайд 38 Гамильтоновым путём (циклом) графа G называется путь (цикл),
проходящий через каждую его вершину только один раз. Граф,
содержащий гамильтонов цикл, называется гамильтоновым. В графе на рисунке путь (V3,V4,V1,V2,V5) является гамильтоновым, а путь (V2,V3,V4,V1,V2,V5) не является гамильто-новым.V4
V1
V2
V5
V3
Слайд 39 Задача 17 «О кёнигсбергских мостах» (Эйлера). Необходимо обойти
все 7 мостов так, чтобы на каждом побывать только
один раз и вернуться к началу пути.С
D
A
B
A
D
B
С
Слайд 40
Решение.
Представим задачу в виде графа, в котором острова
и берега обозначим точками, т.е. они будут вершинами графа.
Мосты будут рёбрами графа.Поскольку необходимо пройти по всем мостам по одному разу и вернуться туда, откуда начали обход мостов, это значит, что нужно по всем рёбрам графа пройти по одному разу, т.е. образовать эйлеров цикл.
Следовательно, нужно проверить, является ли рассматриваемый граф эйлеровым.
Слайд 41 Но в теореме 3.6. говорится о том, что
для того чтобы граф был эйлеровым необходимо и достаточно,
чтобы граф был связным, и все вершины были чётные, т.е. чтобы из каждой вершины исходило чётное количество рёбер.Если посчитать рёбра, то увидим, что вершины А и В, которыми обозначены берега, имеют степень 3, следовательно, они нечётные.
Таким образом, условие теоремы не выполнено, значит ответ задачи отрицательный: невозможно обойти все мосты по одному разу и вернуться в исходную точку.
Слайд 42
2.2. Операции над графами
Объединением графов
и называется граф , множество вершин которого
, а множество рёбер .Пересечением графов и называется граф , для которого - множество рёбер, а - множество вершин.
Кольцевой суммой двух графов называется граф , порождённый множеством вершин и множеством рёбер , т.е. множеством рёбер, содержащихся либо в , либо в , но не в .
Слайд 44 Подграфом графа называется граф
, все вершины и рёбра которого являются подмножествами
множества вершин и рёбер графа G.Компонентой связности неориенти-рованного графа называется его подграф с множеством вершин и множеством рёбер , инци-дентных только вершинам из множества , причём ни одна вершина из не смеж-на с вершинами из множества .
Слайд 46
2.3. Деревья. Лес. Бинарные деревья
Деревом называют конечный связный
граф с выделенной вершиной (корнем), не имеющий циклов.
0-й
ярус1-й ярус
2-й ярус
3-й ярус
4-й ярус
V0
Слайд 47 Для каждой пары вершин дерева – узлов –
существует единственный маршрут, поэтому вершины удобно классифицировать по степени
удалённости от корневой вершины.Расстояние до корневой вершины называется ярусом s вершины, .
Теорема 2.7. Граф является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:
граф связен и не содержит циклов;
граф не содержит циклов и имеет n – 1 ребро;
Слайд 48
граф связен и имеет п – 1 ребро;
граф
не содержит циклов, но добавление ребра между несмежными вершинами
приводит к появлению одного и только одного элементарного цикла;граф связный, но утрачивает это свойство после удаления любого ребра;
в графе всякая пара вершин соединена цепью, и только одной.
Висячие вершины, за исключением корневой, называются листьями.
Слайд 49 Упорядоченное объединение деревьев представляет собой несвязный граф, называемый
лесом.
Остовом связного графа G называется любой его подграф,
содержащий все вершины графа G и являющийся деревом.Кодеревом остова Т графа G называется дополнение Т до G, т.е. такой его подграф, который содержит все его вершины и только те его рёбра, которые не входят в Т.
Слайд 50 При описании деревьев принято использовать термины: отец, сын,
предок, потомок.
Каждая вершина дерева называется узлом, причём каждый узел
является корнем дерева, состоящего из поддеревьев. Узел k-го яруса называется отцом узла (k + 1)–го яруса, если они смежны. Узел (k + 1)–го яруса называется сыном узла k-го яруса. Два узла, имеющие одного отца, называются братьями. Упорядоченным деревом называется дерево, в котором поддеревья каждого узла образуют упорядоченное подмножество.
Слайд 51
V3
V5
V1
Для упорядоченных деревьев принята терминология:
старший и младший сын для обозначения соответственно первого и
последнего сыновей некоторого узла.V0 (предок)
V2 (потомок)
V4 (отец V6 и V7)
V6 (старший сын V4)
V7 (младший сын V4)
Слайд 52 Деревья, в которых каждый узел либо является листом,
либо образует два поддерева: левое и правое, называются бинарными
деревьями и используются при делении множества на два взаимоисключающих подмножества по какому-то признаку (дихотомическое деление).Бинарное дерево уровня n называется полным, если каждый его узел уровня n является листом, а каждый узел уровня меньше, чем n, имеет непустое левое и правое поддеревья.
Слайд 54
Цикломатическое число графа
Цикломатическим числом неориентированного графа G
называется число ,
где - число его рёбер;
-
число связных компонент графа; - число вершин.
Цикломатическое число показывает, сколько рёбер нужно удалить из графа, чтобы в нём не стало циклов.
Слайд 55
3.4. Способы задания графа.
Изоморфные графы
Геометрическое представление плоского
графа называется его реализацией.
При переходе от алгебраического способа (способа
задания графа дугами путём указания вершин, которым они инцидентны) к геометрическому одному и тому же графу могут соответствовать различные изображения – изоморфные графы. Граф можно задавать таблицей, состоящей из n строк (вершины) и т столбцов (рёбра).
Одним из самых распространённых способов задания графа является матричный способ.
Слайд 56 Матрицей инцидентности называется таблица В, состоящая из n
строк (вершины) и т столбцов (рёбра), в которой:
для неориентированного
графа:, если вершина инцидентна ребру ;
, если вершина не инцидентна ребру ;
для ориентированного графа:
, если вершина является началом дуги ;
, если вершина не инцидентна дуге ;
, если вершина является концом дуги.
Слайд 57 Матрицей смежности графа без кратных рёбер называется квадратная
матрица А порядка n, в которой:
, если
;, если .
При восстановлении графа по его матрице инцидентности можно получить граф лишь с точностью до изоморфизма.
Слайд 58 Задача. Пусть граф G задан матрицей смежности А.
Построить диаграмму этого графа, если
Решение. Поскольку матрица А несимметрична
(например ), то она может задавать только ориентиро- ванный граф.V1
V2
V3
V4
V5
V6
