🗊Презентация Основные понятия теории графов. (Лекции 11-12)

Категория: Математика
Нажмите для полного просмотра!
Основные понятия теории графов. (Лекции 11-12), слайд №1Основные понятия теории графов. (Лекции 11-12), слайд №2Основные понятия теории графов. (Лекции 11-12), слайд №3Основные понятия теории графов. (Лекции 11-12), слайд №4Основные понятия теории графов. (Лекции 11-12), слайд №5Основные понятия теории графов. (Лекции 11-12), слайд №6Основные понятия теории графов. (Лекции 11-12), слайд №7Основные понятия теории графов. (Лекции 11-12), слайд №8Основные понятия теории графов. (Лекции 11-12), слайд №9Основные понятия теории графов. (Лекции 11-12), слайд №10Основные понятия теории графов. (Лекции 11-12), слайд №11Основные понятия теории графов. (Лекции 11-12), слайд №12Основные понятия теории графов. (Лекции 11-12), слайд №13Основные понятия теории графов. (Лекции 11-12), слайд №14Основные понятия теории графов. (Лекции 11-12), слайд №15Основные понятия теории графов. (Лекции 11-12), слайд №16Основные понятия теории графов. (Лекции 11-12), слайд №17Основные понятия теории графов. (Лекции 11-12), слайд №18Основные понятия теории графов. (Лекции 11-12), слайд №19Основные понятия теории графов. (Лекции 11-12), слайд №20Основные понятия теории графов. (Лекции 11-12), слайд №21Основные понятия теории графов. (Лекции 11-12), слайд №22Основные понятия теории графов. (Лекции 11-12), слайд №23Основные понятия теории графов. (Лекции 11-12), слайд №24Основные понятия теории графов. (Лекции 11-12), слайд №25Основные понятия теории графов. (Лекции 11-12), слайд №26Основные понятия теории графов. (Лекции 11-12), слайд №27Основные понятия теории графов. (Лекции 11-12), слайд №28Основные понятия теории графов. (Лекции 11-12), слайд №29Основные понятия теории графов. (Лекции 11-12), слайд №30
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Основные понятия теории графов. (Лекции 11-12). Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Основные понятия теории графов. (Лекции 11-12), слайд №1
Описание слайда:

Слайд 2


Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами. Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами.
Описание слайда:
Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами. Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами.

Слайд 3


Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek. Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek. Ребра с одинаковыми концевыми вершинами называются параллельными (e1,e4 ). Петля– замкнутое ребро(e5). Ребро, принадлежащее вершине, называется инцидентным (ребро e1 инцидентно вершинам v1 и v2).
Описание слайда:
Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek. Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek. Ребра с одинаковыми концевыми вершинами называются параллельными (e1,e4 ). Петля– замкнутое ребро(e5). Ребро, принадлежащее вершине, называется инцидентным (ребро e1 инцидентно вершинам v1 и v2).

Слайд 4


Изолированная вершина не инцидентна ни одному ребру (v3). Изолированная вершина не инцидентна ни одному ребру (v3). Две вершины смежны, если они являются концевыми вершинами некоторого ребра (v1, v4). Если два ребра имеют общую концевую вершину, они называются смежными (e1, e2).
Описание слайда:
Изолированная вершина не инцидентна ни одному ребру (v3). Изолированная вершина не инцидентна ни одному ребру (v3). Две вершины смежны, если они являются концевыми вершинами некоторого ребра (v1, v4). Если два ребра имеют общую концевую вершину, они называются смежными (e1, e2).

Слайд 5


Подграф – любая часть графа, сама являющаяся графом. Подграф – любая часть графа, сама являющаяся графом.
Описание слайда:
Подграф – любая часть графа, сама являющаяся графом. Подграф – любая часть графа, сама являющаяся графом.

Слайд 6


Граф G=(V,E) называется простым, если он не содержит петель и параллельных ребер. Граф G=(V,E) называется простым, если он не содержит петель и параллельных ребер.
Описание слайда:
Граф G=(V,E) называется простым, если он не содержит петель и параллельных ребер. Граф G=(V,E) называется простым, если он не содержит петель и параллельных ребер.

Слайд 7


Основные понятия теории графов. (Лекции 11-12), слайд №7
Описание слайда:

Слайд 8


Граф G с петлями и кратными ребрами называется псевдограф. Граф G с петлями и кратными ребрами называется псевдограф.
Описание слайда:
Граф G с петлями и кратными ребрами называется псевдограф. Граф G с петлями и кратными ребрами называется псевдограф.

Слайд 9


Граф G, рёбра которого не имеют определённого направления, называется неориентированным. Граф G, рёбра которого не имеют определённого направления, называется неориентированным.
Описание слайда:
Граф G, рёбра которого не имеют определённого направления, называется неориентированным. Граф G, рёбра которого не имеют определённого направления, называется неориентированным.

Слайд 10


Граф G, имеющий определённое направление, называется ориентированным графом или орграфом. Граф G, имеющий определённое направление, называется ориентированным графом или орграфом. Ребра, имеющие направление, называются дугами.
Описание слайда:
Граф G, имеющий определённое направление, называется ориентированным графом или орграфом. Граф G, имеющий определённое направление, называется ориентированным графом или орграфом. Ребра, имеющие направление, называются дугами.

Слайд 11


1) Явное задание графа как алгебраической системы. 1) Явное задание графа как алгебраической системы. Чтобы задать граф, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. {{a,b},{b,c},{a,c},{c,d}}
Описание слайда:
1) Явное задание графа как алгебраической системы. 1) Явное задание графа как алгебраической системы. Чтобы задать граф, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. {{a,b},{b,c},{a,c},{c,d}}

Слайд 12


2) Геометрический. 2) Геометрический.
Описание слайда:
2) Геометрический. 2) Геометрический.

Слайд 13


3) Матрица смежности. 3) Матрица смежности. Элементы Aij матрицы смежности A равны количеству ребер между рассматриваемыми вершинами.
Описание слайда:
3) Матрица смежности. 3) Матрица смежности. Элементы Aij матрицы смежности A равны количеству ребер между рассматриваемыми вершинами.

Слайд 14


Для неорграфа G, представленного на рисунке, матрица смежности имеет вид: Для неорграфа G, представленного на рисунке, матрица смежности имеет вид:
Описание слайда:
Для неорграфа G, представленного на рисунке, матрица смежности имеет вид: Для неорграфа G, представленного на рисунке, матрица смежности имеет вид:

Слайд 15


Для орграфа G, представленного на рисунке, матрица смежности имеет вид: Для орграфа G, представленного на рисунке, матрица смежности имеет вид:
Описание слайда:
Для орграфа G, представленного на рисунке, матрица смежности имеет вид: Для орграфа G, представленного на рисунке, матрица смежности имеет вид:

Слайд 16


4) Матрица инцидентности. 4) Матрица инцидентности. Матрица инцидентности В –это таблица, строки которой соответствуют вершинам графа, а столбцы - ребрам. Элементы матрицы определяются следующим образом:
Описание слайда:
4) Матрица инцидентности. 4) Матрица инцидентности. Матрица инцидентности В –это таблица, строки которой соответствуют вершинам графа, а столбцы - ребрам. Элементы матрицы определяются следующим образом:

Слайд 17


1) для неорграфа 1) для неорграфа 1, если вершина vi инцидентна ребру ej; bij= 0, в противном случае
Описание слайда:
1) для неорграфа 1) для неорграфа 1, если вершина vi инцидентна ребру ej; bij= 0, в противном случае

Слайд 18


2) для орграфа 2) для орграфа -1, если ребро ej входит в вершину vi ; 1, если ребро ej выходит из вершины vi ; bij= 2, если ребро ej –петля из вершины vi ; 0, если ej и vi не инцидентны.
Описание слайда:
2) для орграфа 2) для орграфа -1, если ребро ej входит в вершину vi ; 1, если ребро ej выходит из вершины vi ; bij= 2, если ребро ej –петля из вершины vi ; 0, если ej и vi не инцидентны.

Слайд 19


Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i  k. Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i  k.
Описание слайда:
Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i  k. Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i  k.

Слайд 20


Маршрут называется открытым, если его концевые вершины различны (v1, e1, v2, e2, v3, e3, v6, e9, v5, e7, v3, e11, v6). Маршрут называется открытым, если его концевые вершины различны (v1, e1, v2, e2, v3, e3, v6, e9, v5, e7, v3, e11, v6). Маршрут называется замкнутым, если его концевые вершины совпадают (v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1).
Описание слайда:
Маршрут называется открытым, если его концевые вершины различны (v1, e1, v2, e2, v3, e3, v6, e9, v5, e7, v3, e11, v6). Маршрут называется открытым, если его концевые вершины различны (v1, e1, v2, e2, v3, e3, v6, e9, v5, e7, v3, e11, v6). Маршрут называется замкнутым, если его концевые вершины совпадают (v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1).

Слайд 21


Маршрут называется цепью, если все его ребра различны. Маршрут называется цепью, если все его ребра различны. Цепь называется простой, если ее концевые вершины различны(v1, e1, v2, e2, v3, e8, v6, e11, v3). Цепь называется замкнутой, если ее концевые вершины совпадают (v1,e1,v2,e2,v3,e7,v5,e3,v2,e4,v4,e5,v1).
Описание слайда:
Маршрут называется цепью, если все его ребра различны. Маршрут называется цепью, если все его ребра различны. Цепь называется простой, если ее концевые вершины различны(v1, e1, v2, e2, v3, e8, v6, e11, v3). Цепь называется замкнутой, если ее концевые вершины совпадают (v1,e1,v2,e2,v3,e7,v5,e3,v2,e4,v4,e5,v1).

Слайд 22


Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3). Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3). Цикл – это замкнутая цепь ( простой цикл, если цепь простая) (v1,e1,v2,e3,v5,e6,v4,e5,v1). Число ребер в пути называется длиной пути. Аналогично определяется длина цикла.
Описание слайда:
Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3). Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3). Цикл – это замкнутая цепь ( простой цикл, если цепь простая) (v1,e1,v2,e3,v5,e6,v4,e5,v1). Число ребер в пути называется длиной пути. Аналогично определяется длина цикла.

Слайд 23


1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1. 1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1. 2. Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, — неверно. 3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.
Описание слайда:
1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1. 1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1. 2. Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, — неверно. 3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.

Слайд 24


Две вершины vi и vj называются связанными в графе G, если в нем существует путь vi—vj. Вершина связана сама с собой. Две вершины vi и vj называются связанными в графе G, если в нем существует путь vi—vj. Вершина связана сама с собой. Граф называется связным, если в нем существует путь между каждой парой вершин. Компонента связности – максимальный связный подграф в графе.
Описание слайда:
Две вершины vi и vj называются связанными в графе G, если в нем существует путь vi—vj. Вершина связана сама с собой. Две вершины vi и vj называются связанными в графе G, если в нем существует путь vi—vj. Вершина связана сама с собой. Граф называется связным, если в нем существует путь между каждой парой вершин. Компонента связности – максимальный связный подграф в графе.

Слайд 25


Степенью deg(vj) вершины vj называется число инцидентных ей ребер, т. е. вершин в ее окружении. Степенью deg(vj) вершины vj называется число инцидентных ей ребер, т. е. вершин в ее окружении. Максимальная и минимальная степени вершин графа G обозначаются символами (G) и (G) соответственно: (G)= (G)= Граф G=(V,E) называется регулярным или однородным (степени r), если степени всех его вершин одинаковы. Степенью регулярного графа называется степень его вершин.
Описание слайда:
Степенью deg(vj) вершины vj называется число инцидентных ей ребер, т. е. вершин в ее окружении. Степенью deg(vj) вершины vj называется число инцидентных ей ребер, т. е. вершин в ее окружении. Максимальная и минимальная степени вершин графа G обозначаются символами (G) и (G) соответственно: (G)= (G)= Граф G=(V,E) называется регулярным или однородным (степени r), если степени всех его вершин одинаковы. Степенью регулярного графа называется степень его вершин.

Слайд 26


Утверждение («лемма о рукопожатиях») Утверждение («лемма о рукопожатиях») Сумма всех вершин графа – четное число, равное удвоенному числу ребер: Интерпретация леммы: поскольку в каждом рукопожатии участвуют две руки,то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала). Следствие В любом графе число вершин нечетной степени четно
Описание слайда:
Утверждение («лемма о рукопожатиях») Утверждение («лемма о рукопожатиях») Сумма всех вершин графа – четное число, равное удвоенному числу ребер: Интерпретация леммы: поскольку в каждом рукопожатии участвуют две руки,то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала). Следствие В любом графе число вершин нечетной степени четно

Слайд 27


Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов. Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов. Если граф G изоморфен геометрическому графу G' в Rn, то G' называется геометрической реализацией графа G в пространстве Rn.
Описание слайда:
Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов. Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов. Если граф G изоморфен геометрическому графу G' в Rn, то G' называется геометрической реализацией графа G в пространстве Rn.

Слайд 28


Соответствие вершин: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’; Соответствие вершин: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’; Соответствие ребер: e1e1’, e3e2’, e5e4’, e2e5’, e4e6’, e6e3’.
Описание слайда:
Соответствие вершин: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’; Соответствие вершин: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’; Соответствие ребер: e1e1’, e3e2’, e5e4’, e2e5’, e4e6’, e6e3’.

Слайд 29


Отношение изоморфизма является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно. Отношение изоморфизма является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно.
Описание слайда:
Отношение изоморфизма является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно. Отношение изоморфизма является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно.

Слайд 30


Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки (например номера 1, 2, …, n). Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки (например номера 1, 2, …, n). Абстрактный (или непомеченный) граф – это класс изоморфных графов.
Описание слайда:
Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки (например номера 1, 2, …, n). Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки (например номера 1, 2, …, n). Абстрактный (или непомеченный) граф – это класс изоморфных графов.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию