Page 61 - 4496
P. 61
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.
3. 10 Маршрути, ланцюги, та цикли
Теорема. У графі число вершин з непарної ступенем
парне.
Доказ заснований на тому , що будь-яка дуга пов'язана з
двома вершинами, значить, сума ступенів усіх вершин удвічі
більша числа вершин, тобто завжди парна.
Для підмножини вершин 'A A безліч дуг, що виходять
+
-
з 'A, позначають ‘A , а безліч дуг, що заходять у 'A – A .
58
