Комбинаторика Скачать
презентацию
<<  Виды графов Применение теории графов  >>
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
Основы теории графов
В ориентированном графе параллельные дуги бывают двух типов: строго
В ориентированном графе параллельные дуги бывают двух типов: строго
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 4 1-3-4 23 7 1-2-5-7
Графовая модель образовательного учреждения
Графовая модель образовательного учреждения
Фото из презентации «Теория графов» к уроку алгебры на тему «Комбинаторика»

Автор: rodichev. Чтобы познакомиться с фотографией в полном размере, нажмите на её эскиз. Чтобы можно было использовать все фотографии на уроке алгебры, скачайте бесплатно презентацию «Теория графов» со всеми фотографиями в zip-архиве размером 498 КБ.

Скачать презентацию

Теория графов

содержание презентации «Теория графов»
Сл Текст Эф Сл Текст Эф
1Основы теории графов. V-множество вершин, E-0 7различных ребер. Простой цикл - маршрут, в котором0
множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, начальная и конечная вершины совпадают, а все остальные
Е, f) V,E – множества, отображение инциденции f: Е? вершины различны.
V&V множества Е в V&V. 8Основы теории графов. Древовидные графы.0
2Основы теории графов. V={A,В,С,D,F,Н,P} – множество0 Онределение 1. Деревом называется конечный связный граф
точек, E={a,b,с,d,e,f,g,h,p,l} – множество линий f: Е? без циклов. Онределение 2. Деревом называется конечный
V&V, определяется по закону f: a?(H&H), граф, любые две вершины которого соединяются
b?(P&F), c?(B&C), d?(A&B), e?(P&F), единственной цепью. Определение 3. Деревом называется
f?(B&H), g?(B&H), h?(A&H), p?(A&B), конечный связный граф, для которого количество ребер на
l?(A&B). единицу меньше количества вершин. Определение 4.
3Основы теории графов. Определение инцидентности.0 Деревом называется конечный граф, обладающий свойством:
Пусть задан абстрактный граф G(V, Е, f). Если граф не содержит циклов, но добавление ребра между
отображение f сопоставляет ребру е пару вершин любыми не смежными вершинами приводит к появлению
(х1&х2) , т.е. f(e) = (х1&х2), то ребро е цикла.
инцидентно вершинам х1 и х2. «ребро е соединяет вершины 9Основы теории графов. Уникурсальные графы Задача0
x1 и x2» «вершины x1 и x2 являются граничными точками Эйлера о кенигсбергских мостах Можно ли пройти по всем
ребра е». Если f(е) = (x&x), то ребро называется мостам, изображенным на рисунке, так, чтобы на каждом
петлей в вершине х. Определение смежности. Две вершины из них побывать лишь один раз и вернуться к тому месту,
x1 и x2 графа G(V, Е, f) называются смежными, если в откуда началась прогулка?
графе существует ребро е, инцидентное этим вершинам. 10Основы теории графов. Уникурсальные графы Граф0
Два ребра графа называются смежными, если существует называется уникурсальным графом (или эйлеровой линией),
вершина, инцидентная обоим этим ребрам. если все его ребра можно включить либо в простой цикл,
4Основы теории графов. Степенью вершины графа0 либо в простую цепь. Признаки уникурсальных графов:
называется количество инцидентных ей ребер (для петли Лемма. Если связный граф имеет более двух нечетных
степень подсчитывается дважды). Вершины графа вершин, то он не уникурсален. Теорема 1. Связный граф
называются четными или нечетными в зависимости от является эйлеровым циклом тогда и только тогда, когда
четности их степеней. Теорема 1. В любом конечном графе он имеет только четные вершины. При этом начало и конец
G(V, Е) количество нечетных вершин — четно. Сумма уникурсального пути совпадают и могут находиться в
степеней всех вершин равна удвоенному числу ребер любой вершине графа. Теорема 2. Связный граф является
графа: ? Q(x)=2|E|. эйлеровой цепью тогда и только тогда, когда он имеет
5Основы теории графов. Операции разборки графа:0 ровно две нечетные вершины, а остальные вершины этого
удаление ребра между двумя вершинами графа. 2) удаление графа четны. При этом начало и конец уникурсального
вершины графа вместе со всеми инцидентными ребрами. пути находятся в нечетных вершинах.
Подграфом графа G называется такая его часть G1, 11Основы теории графов. Ориентированные графы. G(V,0
которая получается из графа G при помощи конечного Е, f) V={A,В,С,D,Р} E={a1,a2,…,a12}. Отображение
числа операций разборки вида 2. Суграфом графа G инциденции: f: a1?(A,B); a2?(A,B); a3?(B,C); a4?(B,P);
называется такая его часть G1, которая получается из a5?(P,C); a6?(D,C); a7?(D,C); a8?(A,P); a9?(P,D);
графа G при помощи конечного числа операций разборки a10?(A,D); a11?(D,D); a12?(D,D).
вида 1. 12В ориентированном графе параллельные дуги бывают0
6Основы теории графов. Пример операций разборки.0 двух типов: строго параллельные (одинаково
7Основы теории графов. G(V, Е, f) V={А1,А2,…,Аn}0 ориентированные) нестрого параллельные (ориентированные
E={a1,a2,…,an}. Конечная последовательность ребер графа по-разному).
a1,a2,…,ak (не обязательно различных) называется 13Ответ: 2 1-2 20 5 1-2-5 40 3 1-3 15 6 1-3-4-6 43 40
маршрутом длины k, если граничные точки двух соседних 1-3-4 23 7 1-2-5-7 49. Задача выбора кратчайшего
ребер последовательности совпадают. Маршрут называется маршрута.
замкнутым, если его начальная и конечная вершины 14Графовая модель образовательного учреждения.0
совпадают. В противном случае маршрут незамкнутый. Цепь Пользователи образовательных услуг (П). Преподаватели и
- незамкнутый маршрут, состоящий из последовательности сотрудники (работники) (Р). Инфраструктура (Б).
различных ребер. Простая цепь - маршрут, который не Комплекс нормативно-правовых актов (Н). Информационные
проходит дважды через одну и ту же вершину. Цикл - технологии (И).
замкнутый маршрут, состоящий из последовательности
14 «Теория графов» | Теория графов 0
http://900igr.net/fotografii/algebra/Teorija-grafov/Teorija-grafov.html
cсылка на страницу
Урок

Алгебра

34 темы
Фото
Презентация: Теория графов | Тема: Комбинаторика | Урок: Алгебра | Вид: Фото