«Дополнение и планарность графа»



Скачать 11.03 Kb.
Дата11.10.2012
Размер11.03 Kb.
ТипДокументы
Министерство образования российской федерации

САРАПУЛЬСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (филиал)

Государственного образовательного учреждения высшего профессионального образования

«Ижевский государственный технический университет»

Имени М.Т. Калашникова.
Кафедра КиПР

ОТЧЁТ

На тему: «Дополнение и планарность графа».

Выполнил: Втюрин М.В. Б02-781-1

Проверил: Максимов М. В.


Сарапул

2012
Задание: найти дополнение графа.

Определить, планарен ли граф и его дополнение (доказать рисунком).
Решение:

Вывод: Планарный граф – это граф, который можно изобразить на плоскости без пересечения ребер.

В теории графов дополнением или обратным к графу G называется такой граф H, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Чтобы найти обратный граф, дополните данный граф до полного и удалите все ребра, которые уже были до этого.

Похожие:

«Дополнение и планарность графа» icon«Дополнение графа»
Государственного образовательного учреждения высшего профессионального образования
«Дополнение и планарность графа» iconДискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах
Понятие неориентированного графа. Способы задания графа. Матрицы смежности. Путь в графе. Цикл в графе. Связный граф. Компоненты...
«Дополнение и планарность графа» iconПредставление информации в форме графа
Цель: Познакомить учащихся с понятием графа, историей возникновения и развития теории графов, представлением информации в форме графа...
«Дополнение и планарность графа» iconАлгоритм Зыкова
Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный...
«Дополнение и планарность графа» iconКомбинаторика, 11. 03 Семинар 10
Пусть V –множество вершин графа G(V, X), XVV – множество ребер графа G(V, X). Если
«Дополнение и планарность графа» iconСеминар 11. Матрица a =( a ij ), где a ij
Матрица A=(aij), где aij=1, если (VI, vj)X, aij =0, если (VI, vj)X, называется матрицей смежности графа G(V, X). Для неориентированного...
«Дополнение и планарность графа» icon11 класс Часть I задания части I выполняются во время проведения зачётной работы
Для заданного графа выполните следующие задания (при необходимости пронумеруйте вершины графа)
«Дополнение и планарность графа» iconЛекция №14-15 Алгоритмы на графах Определение графа Графом
Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть "множеством вершин", а — семейством ребер...
«Дополнение и планарность графа» iconПеречислите способы задания графов. Что такое матрица инциденций графа?
Оцените число ребер графа через число вершин и число компонент связности, если в графе р=11, k=3
«Дополнение и планарность графа» iconПрограмма к экзамену по курсу Дискретная математика Булевы функции
Алгоритм построения остовного дерева графа, алгоритм построения циклового базиса графа
Разместите кнопку на своём сайте:
ru.convdocs.org


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