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

Комбинаторика Скачать презентацию
<< Виды графов		Применение теории графов >>

Основы теории графов	Основы теории графов	Основы теории графов	Основы теории графов	Основы теории графов
Основы теории графов				В ориентированном графе параллельные дуги бывают двух типов: строго
Ответ: 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 4	0
	маршрутом длины k, если граничные точки двух соседних			1-3-4 23 7 1-2-5-7 49. Задача выбора кратчайшего
	ребер последовательности совпадают. Маршрут называется			маршрута.
	замкнутым, если его начальная и конечная вершины		14	Графовая модель образовательного учреждения.	0
	совпадают. В противном случае маршрут незамкнутый. Цепь			Пользователи образовательных услуг (П). Преподаватели и
	- незамкнутый маршрут, состоящий из последовательности			сотрудники (работники) (Р). Инфраструктура (Б).
	различных ребер. Простая цепь - маршрут, который не			Комплекс нормативно-правовых актов (Н). Информационные
	проходит дважды через одну и ту же вершину. Цикл -			технологии (И).
	замкнутый маршрут, состоящий из последовательности
14	«Теория графов» \| Теория графов				0