Инструменты пользователя

Инструменты сайта


examination:diskretka:question3

Вопрос №3. Основные действия с графами: объединение, несвязная сумма, пересечение графов. Подграф, порожденный подмножествами вершин и ребер. Вычитание ребер и вершин. Дополнение подграфа в графе

ВАЖНО!
Для адекватного просмотра больших картинок через Opera Mini нужно:
1) залезть в параметры
2) поставить качество изображений на «высокое»
3) убрать галочку с «мобильный вид»
4) сохранить и перезагрузить страницу

Пусть есть два графа: Г1=(V1,E1,I1), Г2=(V2,E2,I2)

1)Объединение: Г1υГ2:

Пусть v,w принадлежат V1 и V2

Для любого e из E1∩E2 I1(v,e,w)⇔I2(v,e,w) (неиспользование одинаковых имён для различных рёбер)

Г=Г1υГ2 : V=V1υV2; E=E1υE2; I входит в VxExV, то есть I=I1υI2;

Общий случай:



Замечание: прямая сумма графов определена с точностью до изоморфизма, т.к. сами графы Г'1 и Г'2 определены с точностью до изоморфизма. Без труда можно определить прямую сумму произвольного семейства графов.




examination/diskretka/question3.txt · Последние изменения: 2014/01/15 08:14 (внешнее изменение)