Cтраница 2
Пусть ребра простого графа, полученного соединением каждой из т вершин одного множества с каждой из п вершин другого, ориентируются случайным образом, а С ( т, п означает число контуров длины 4 в полученном ориентированном графе. [16]
Хроматический индекс простого графа не больше, чем на единицу, превосходит максимальную из степеней его вершин. [17]
При рассмотрении простых графов изоморфизм между ними часто определяют как взаимно однозначное соответствие между множествами их вершин, сохраняющее отношение смежности. [18]
Характеристический многочлен простого графа восстанавливаем. [19]
Сколько существует простых графов с 2п вершинами и п ребрами, компоненты связности которых являются изолированными ребрами. [20]
Автоморфизмом ф простого графа G называется взаимно однозначное отображение множества вершин графа G на себя, обладающее тем свойством, что вершины ф ( v) ир ( о)) смежны тогда и только тогда, когда смежны вершины о и да. [21]
Пусть в простом графе ( Мъ М2, N) выделено уже паросочетание N, I ( N) с: Мг - множество начал дуг паро-сочетания, J ( N) с М2 - множество концов. [22]
Если в простом графе с п ( 3) вершинами р ( о) nil для любой вершины v, то граф G является гамильтоновым. [23]
Пусть G - простой граф, и пусть Ра ( k) - число способов, которыми можно окрасить вершины графа G, используя k красок и соблюдая условие: никакие две смежные вершины не должны иметь один и тот же цвет. Будем ( временно) называть Ра хроматической функцией графа G. Например, если G - граф, изображенный на рис. 21.1, то PQ ( k) k ( k - I) 2, так как среднюю вершину можно окрасить k способами и, следовательно, каждую из концевых вершин - любым из k - 1 способов. [24]
Пусть G - простой граф с п вершинами и т ребрами; дайте подробное доказательство того, что ( i) Po является приведенным многочленом2) степени п; ( ii) коэффициент при fe - 1 равен - т; ( ш) знаки коэффициентов чередуются. [25]
Пусть G - простой граф максимальной степенью k - 1 и М - максимальное паросочетание в нем. Тогда граф G имеет реберную fc - раскраску, при которой паросочетание М образует один цветной класс. [26]
Пусть G - простой граф, имеющий по крайней мере две вершины. Покажите, что G содержит аве вершины с одинаковыми степенями. [27]
Пусть G - простой граф с 2п вершинами, не содержащий треугольников. Индукцией по п докажите, что G содержит не более га2 ребер, и приведите пример, когда эта верхняя граница достигается. Этот результат известен как экстремальная теорема Тураиа. [28]
Пусть G - простой граф; покажите, что если он непланарен, то его реберный граф L ( G) тоже непланарен. [29]
Пусть G - связный простой граф, не являющийся ни полным графом, ни циклическим графом с нечетным числом вершин; можно доказать, что если Я, - наибольшее характеристическое число графа G ( см. упр. [30]