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



Дата04.07.2013
Размер12.8 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