В чём дело?

10

ребра $r$ соединены в $G'$ простой цепочкой — оставшейся часть контура), причем вершины у графа $G'$ — те же, что и у $G$. Если $G'$ еще не является деревом, то есть в $G'$ также имеет контур (рис. 11 б), то мы можем взять произвольное ребро $r_2$ этого контура и, выбросив его, получить с вязый граф $G''$ с тем и же вершинами, что и у $G$, и т. д. Так как число ребер конечно, этот процесс должен на каком-то шаге оставиться; иначе говоря, после выбрасывания какого-то ребра $r_k$ мы получим связный граф $G^*$, содержащий все вершины графа $G$ и уже не имеющий контур, то есть являющийся деревом. Граф $G^*$ называется максимальным деревом графа $G$, а ребра $r_1, r_2, ..., r_k$, которые пришлось выбросить из $G$, чтобы получить максимальное дерево $G^*$, называются перемыками.

Если $B$ — число вершин графа $G$, то максимальное дерево $G^*$ тоже имеет $B$ вершин. Согласно (1), граф $G^*$ имеет $B-1$ ребер, и потому число ребер графа $G$ равно $B-1+k$ (что бы из $G^*$ получить $G$, надо «возвращать» $k$ выбросенных ребер-перемычек). Следовательно,

$$\chi(G) = B - (B-1+k) = 1-k. \quad (2)$$

Так как $k \ge 1$, получаем $\chi(G) \leq 0$. Таким образом, учитывая (1), мы видим, что для любого связного графа $G$ справедливо соотношение

$$\chi(G) \leq 1,$$

причем равенство достигается в том и только в том случае, когда $G$ — дерево.

Далее, согласно (2), число перемычек равно

$$k = 1 - \chi(G).$$

В чём дело?

Согласно «основному свойству первообразной» («Алгебра и начала анализа 9—10», п. 57), если произвольные двух функций совпадают, то эти функции должны отличаться на константу. Произвольные функции:

$$a) y_1 = \frac{1}{1-x^2}$$

$$n) y_2 = \frac{x^2}{1-x^2},$$

заданчи

17. Докажите, что если граф $G$ содержит $l$ компонент, то $\chi(G) \leq l$. В каком случае достигается равенство?

18*. Будем говорить, что в графе $G$ задана система токов, если каждому ребру приписано направление (указываемое стрелкой) и некоторое неотрицательное и село (tok), причем выполяется правлою Кирхофа: для каждой вершины сумма входящих в нее токов равна сумме исходящих. Докажите, что если граф является деревом, то в нем существует только тривалная система токов (все токи равны нулю).

19. Пусть $G$ — связный граф, $G^*$ — его максимальное дерево, а $r_1, r_2, ..., r_k$ — перемычки (то есть ребра графа $G$, не содержащие в $G^*$). Докажите, что если произвольно задается токи на ребрах $r_1, r_2, ..., r_k$, то их можно однозначно дополить токами на остальных ребрах так, чтобы получилась система токов в $G$.

Указание. Для каждой перемычки $r_i$ существует единицу контур, содержащей ее и не содержащий других перемычок. Если пустить по этому контуру ток такой величины и направления, как указано на перемычке $r_i$, а затем взять сумму всех этих «kontурных токов», то мы и получим требуемую систему токов на графе $G$. Если бы существовали две различные системы токов, совпадующие на перемычках, то их разность была бы нетривиальной системой токов на дереве $G^*$.

Итак, экскурсия по теории графов, проведенная под крылом англела топологии, оказывается полезной для решения математических и даже физических задач. Мы надемемся, что она была приятной и вы захотите ее продолжить. В следующем номере журнала мы оставимся на более глубоких вопросах топологии графов. Но для их изучения нам придется более внимательно прислушаться к «дьяводу абстрактной алгебры».

В чем дело?

Согласно «основному свойству первообразной» («Алгебра и начала анализа 9—10», п. 57), если произвольные двух функций совпа��ают, то эти функции должны отличаться на константу. Произвольные функции:

$$a) y_1 = \frac{1}{1-x^2}$$

$$n) y_2 = \frac{x^2}{1-x^2},$$

заданчи

17. Докажите, что если граф $G$ содержит $l$ компонент, то $\chi(G) \leq l$. В каком случае достигается равенство?

18*. Будем говорить, что в графе $G$ задана система токов, если каждому ребру приписано направление (указываемое стрелкой) и некоторое неотрицательное и село (tok), причем выполяется правлою Кирхофа: для каждой вершины сумма входящих в нее токов равна сумме исходящих. Докажите, что если граф является деревом, то в нем существует только тривалная система токов (все токи равны нулю).

19. Пусть $G$ — связный граф, $G^*$ — его максимальное дерево, а $r_1, r_2, ..., r_k$ — перемычки (то есть ребра графа $G$, не содержащие в $G^*$). Докажите, что если произвольно задается токи на ребрах $r_1, r_2, ..., r_k$, то их можно однозначно дополить токами на остальных ребрах так, чтобы получилась система токов в $G$.

Указание. Для каждой перемычки $r_i$ существует единицу контур, содержащая ее и не содержащий других перемычок. Если пустить по этому контуру ток такой величины и направления, как указано на перемычке $r_i$, а затем взять сумму этих «kontурных токов», то мы и получим требуемую систему токов на графе $G$. Если бы所述ная система токов, совпадшие на перемычках, то их разность была бы нетривиальной системы токов на дереве $G^*$.

Итак, экскурсия по теории графов, проведенная под крылом англела топологии, оказывается полезной для решения математических и даже физических задач. Мы надемемся, что она была приятной и вы захотите ее продолжить. В следующем номере журнала мы оставимся на более глубоких вопросах топологии графов. Но для их изучения нам придется более внимательно прислушаться к «дьяводу абстрактной алгебры».

Н. Алексаандров,
П. Смирнов