LINUX.ORG.RU

Теория графов (не программирование, не линукс)


0

0

Приветствую. Прошу помощи не связанной с программированием и линукс. Задача из курса теории графов, я ее впринципе доказал, остался один момент который строго показать не могу, возможно из-за того что ошибаюсь. Короче нужно показать 1 из 4 что-то (все остальные связаны через св-во L0(G)+B0(G)=n ):
L0(G)+L0(не G)=n
B0(G)+B0(не G)=n
L0(G)=B0(не G)
B0(G)=L0(не G)
где L0 - число вершинной независимости графа, B0 - число вершинного покрытия, G - НЕПОЛНЫЙ(!!!) граф, не G - дополнение к графу G, n - кол-во вершин в графе G.
Причом вроде это доказывается через определения вершинной независимости и определения дополнения графа.
Благодарю всех кто поможет.

П.С. для троллей - началась сессия, да я студент.

★★

Ответ на: комментарий от dilmah

Да я с этого начал изучать:) Там не показана связь вершинного покрытия графа G с его дополнением, мне именно это надо, а как оно считается в пределах самого графа это более-менее понятно

DDR ★★
() автор топика
Ответ на: комментарий от DDR

ну представь себе что у тебя есть вершинное покрытие -- по определению это значит что любое ребро обязано его касаться. Теперь берем дополнение к покрытию. Очевидно, что оно независимо -- там не может быть ни одного ребра, потому что тогда это ребро не касалось бы покрытия.

dilmah ★★★★★
()

никто не против таких тем в Девелопменте, но не надо злоупотреблять.

Pi ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.