Cтраница 2
Для доказательства достаточности предположим сначала, что т четно. Если можно раскрасить граф N, то можно, конечно, раскрасить и граф N. Nn - факторы графа N; каждый из них представляет собой совокупность многоугольников ( циклов), не касающихся друг друга, и, следовательно, каждый Nt может быть раскрашен самое большее тремя цветами. [16]
У кограниц, введенных в разд. В ней показывается, что эти кограницы тесно связаны с / - факторами графов. [17]
Заметим, что несмотря на одинаковую запись структурных чисел матрицы и графа, переход от номеров структурных чисел к элементам определителей матрицы у них осуществляется по-разному. Если область определения отображения, порождаемого структурным числом матрицы, соответствует первым индексам элементов матрицы, а область значений - вторым индексам, то для структурного числа графа область определения - это множество вершин графа, откуда исходят дуги фактора ( пути), а область значений - множество вершин, куда входят эти дуги. В связи с этим члены определителя в случае использования структурных чисел матриц записываются непосредственно по соответствующим отображениям, а при использовании структурных чисел графов получаемые отображения служат для определения путей и факторов графа. Члены определителя получаются уже как сумма весов дуг, входящих в эти пути и факторы. [18]
Во введении профессор Татт говорит о своих первых встречах с теорией графов, в частности, когда он учился в Кембридже. Это не может не вызвать и у меня собственных юношеских воспоминаний. В разговорах математиков, занимавшихся теорией графов, излюбленной была тема о том, что впервые привлекло их внимание к теории графов. Иначе говоря, когда я, еще студентом, стал заниматься научной работой ( тоже в Кембридже), то чувствовал, что должна существовать ветвь математики, изучающая объекты такого рода, а если ее нет, то я должен ее создать. Упоминания о бинарных отношениях в курсах алгебры, возможно, способствовали укреплению этой мысли. Насколько мало было известно о положении в теории графов в те времена, видно из такого факта: мне потребовалось несколько недель, чтобы установить, что я не являюсь первооткрывателем в этой области, и услышать об одном существующем руководстве по данному предмету, а именно, о монографии Кенига Теория ориентированных и неориентированных графов ( К5т § О. После книги Кенига я ознакомился с несколькими доступными в то время научными статьями по графам и провел много часов в библиотеке, изучая работу проф. Татта о факторах графов, щедро вооружившись цветными карандашами ( особенно, конечно, красными и синими), чтобы рисовать диаграммы, стимулирующие воображение. [19]