Теория Графов

[antacid1]

1. Дополнение.
В книге написано: "Для любой части H графа G существует единственная дополнительная часть (дополнение) T, состоящая из всех ребер графа G, которые не принадлежат Н.

У меня возникла небольшая каша в голове: если объединить T и H, получится полный граф?

2. Всегда ли существует смежностный граф?

3. Маршрут длины n состоит именно из n ребер? (Маршрут S - маршрут длины n, если он соединяет вершины a₀ и a_n)

4. Циклическим может называться только нетривиальный маршрут?

[Swetlana]

а я-то думала, что знаю основные определения из теории графов
это что за книга?

1. "часть" графа, видимо, подграф?
если объединить H и T снова получим G. Каким он был, таким и останется, новые рёбра туда не попадут, т.к. дополнение состоит из рёбер графа G.
То, на что вы подумали, называют вроде "пополнением".

2. А что такое смежностный граф? :blink:

3. Видимо, да.

4. Что такое нетривиальный маршрут? :blink:
Вообще, терминология неустоявшаяся, иногда неправильно переводят. Вот общепринято сейчас, что элементарный путь - путь с различными вершинами, простой - с различными рёбрами.
В неориентированном графе для цикла нужно 3 вершины, в ориентированном - достаточно двух.