Операції з частинами графа.
Доповнення частини H називається множина всіх частин графа G, що не належать H.
Об’єднання H1 і H2 визначається так:
V(H1 H2)= V(H1) V(H2); тобто об’єднання вершин і
E(H1 H2)= E (H1) E (H2). об’єднання ребер.
Переріз H1 і H2 визначають аналогічно
V(H1 H2)= V(H1) V(H2);
E(H1 H2)= E(H1) E(H2).
Дві частини H1 і H2 не перерізаються по вершинам, якщо вони не мають спільних вершин, а значить і спільних ребер.
Об’єднання H1 H2 частин, що не перерізаються по вершинам, називають прямою сумою H1 і H2. Частини H1 і H2 не перерізаються по ребрах, якщо E(H1) E(H2)=0.
Дата добавления: 2015-09-27 | Просмотры: 588 | Нарушение авторских прав
|