Плоские графы и теорема Рамсея



Скачать 13.83 Kb.
Дата04.07.2013
Размер13.83 Kb.
ТипДокументы
Плоские графы и теорема Рамсея
Определение 1. Граф, который можно нарисовать так, чтобы его ребра не пересекались нигде, кроме вершин, называется плоским или планарным.
Теорема Эйлера. Для правильно нарисованного связного плоского графа имеет место равенство V-E+F=2.

Правильно нарисованный плоский граф разбивает плоскость на куски. Обозначим число этих кусков через F, число вершин графа через V, число ребер через E.

(Для доказательства вспомните про волейбольную сетку)
1. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
2. Докажите, что для плоского графа верно неравенство 2E 3F.
3. Доказать, что граф на рисунке неплоский.


Определение 2. Граф, каждая вершина которого соединена с любой другой вершиной, называется полным.
4. Каждые 2 из 6 компьютеров соединены проводом. Можно ли все эти провода раскрасить в пять цветов так, чтобы из каждого компьютера выходили 5 проводов одного цвета?
5. Нарисовать плоский граф, имеющий 6 вершина, степень каждой из которых равна а) 3; б) 4.
6. Нарисовать плоский граф, имеющий 8 вершин, степень каждой из которых равна 4.
7. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, неплоский.
8. Докажите, что в любом плоском графе есть вершина, степень которой не превосходит 5.
9. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо «красный», либо «синий» граф не является плоским.
Теорема (Вагнер, Фари, Штейн). Плоский граф можно изобразить так, чтобы все его ребра были отрезками.

Похожие:

Плоские графы и теорема Рамсея iconПояснительная записка: Требования к студентам : курс «Дискретные математические модели»
ЕН. Ф. 01. Плоские графы; эйлеровы графы; гамильтоновы графы; орграфы; сетевые графики; сети Петри
Плоские графы и теорема Рамсея iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Плоские графы и теорема Рамсея iconПланарностъ § 36. Плоские и планарные графы
А так как проводники не изолированы, то они нe должны пересекаться. Аналогичная задача возникает при проектировании железнодорожных...
Плоские графы и теорема Рамсея iconВ вопроснике просьба только пометить указанный ниже номер графы. Не указывайте полного названия графы

Плоские графы и теорема Рамсея iconПрограмма Государственного экзамена по подготовке магистра по направлению «Физика оптических явлений» (510412)
Уравнения Максвелла. Теорема Умова-Пойнтинга Волновое уравнение. Плоские и сферические волны. Поляризация электромагнитных волн;...
Плоские графы и теорема Рамсея icon"Плоские поверхности. Плоскость"
Конспект урока по математике во 2-м классе на тему: "Плоские поверхности. Плоскость"
Плоские графы и теорема Рамсея iconПрограмма составлена кандидатом физ мат наук Барановым В. Н
Симплексы и триангуляция множеств. Нумерации и лемма Шпернера. Теорема Брауера. Теоремы о неподвижной точке в бесконечномерных пространствах....
Плоские графы и теорема Рамсея iconПрограмма составлена кандидатом физ мат наук Петровым Н. Н
Системы типа Каратеодори. Определение. Теорема существования решения задачи Коши. Теорема единственности. Теорема о продолжимости...
Плоские графы и теорема Рамсея iconДифференциальная геометрия и топология
Теорема о неявных функциях (формулировка), теорема об обратном отображении, теорема "об образе"
Плоские графы и теорема Рамсея iconТеорема о неявной функции. Теорема
Теорема: Пусть функция f(x, y) и непрерывны в окрестности точки; кроме того, = 0 и. Тогда такие, что
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org