Банк задач по математике

Задача 2.8.1

Из каждого связного мультиграфа можно удалить вершину (вместе со всеми выходящими из нее рёбрами) так, что он останется связным.

?

Примечание.

?

Граф или мультиграф называется двусвязным, если он отличен от $K_{2}$ и остаётся связным после удаления любой вершины.

Задача 2.8.2

(1)(2)

?

(1)

Частный случай вершинной теоремы Менгера. Любые две различные вершины двусвязного мультиграфа, не соединённые ребром, лежат на некотором несамопересекающемся цикле.

(2)

Верно ли, что для любого пути $P$ в мультиграфе, имеющем не менее трёх вершин, найдётся другой путь в том же мультиграфе с теми же концами, не пересекающийся с $P$ нигде, кроме концов?

Задача 2.8.3

Если в мультиграфе есть хотя бы одно ребро и при удалении любого ребра найдётся путь между вершинами $a$ и $b$ , то в мультиграфе найдутся два пути между вершинами $a$ и $b$ , не имеющие общих рёбер.

?

Задача 2.8.4

(1)(2)(3)

?

(1)

Для любого ребра $u$ двусвязного графа $G$ , отличного от $K_{3}$ , хотя бы один из графов $G-u$ и $G/u$ двусвязен.

(2)

Для любых двух вершин выпуклого многогранника существуют три непересекающихся (нигде, кроме этих вершин) пути по его рёбрам из одной вершины в другую. (Такие графы называют трёхсвязными.)

(3)

Для трёхсвязного графа $G$ с ребром $xy$ (вершины которого — $x,y$ ) граф $G/xy$ трёхсвязен тогда и только тогда, когда граф $G-x-y$ двусвязен.

Задача 2.8.5

(1)(2)

?

(1)

Теорема Уитни (вершинная). Мультиграф остаётся связным после удаления любых $k-1$ вершин тогда и только тогда, когда любые две его вершины можно соединить $k$ путями, пересекающимися только в этих двух вершинах.

(2)

Теорема Менгера (вершинная). Если вершины $a$ и $b$ мультиграфа $G$ , не соединённые ребром, остаются в одной компоненте связности после удаления любых $k-1$ других вершин, то $a$ и $b$ можно соединить $k$ путями, пересекающимися только в этих двух вершинах.

Задача 2.8.6

Вершины $A$ и $B$ графа назовём эквивалентными, если существует такая последовательность вершин $A = A_{0}, A_{1}, \ldots , A_{n} = B$ , что любые две соседние вершины $A_{i}$ и $A_{i+1}$ можно соединить $k$ путями, не имеющими общих промежуточных вершин. Тогда любые две эквивалентные вершины можно соединить $k$ путями, не имеющими общих рёбер.

?