Cтраница 4
Граф, из любой вершины которого можно пройти в любую другую путем, состоящим из ребер, называется связным. Замкнутый путь по ребрам графа называется циклом. Если все циклы графа имеют четную длину, то его вершины можно раскрасить в два цвета так, что вершины одного цвета не соединены ни одним ребром; такой граф называется двудольным. [46]
Бадер [169] определяет планарность графа схемы, когда задан гамильтонов цикл и когда неизвестно его существование. В работе схема представляется графом, у которого вершины соответствуют контактам схемы, а ребра - проводникам. Если задан гамильтонов цикл графа, то в этом случае ребра гамильтонова цикла располагаются таким образом, чтобы он разбивал плоскость на две области - внутреннюю и внешнюю. Строится граф пересечений путем отождествления ребер графа внутри ГЦ вершинам графа пересечений. Далее проверяется, содержит ли граф пересечений циклы нечетной длины, и если содержит, то исходный граф непланарен. Если неизвестно существование ГЦ, то в этом случае граф разбивается на такое число подграфов, чтобы в каждом существовал ГЦ. Если все подграфы планарны, то проверяется планарность подграфов совместно друг с другом и делается заключение о планарности графа. [47]
Пусть О - трехсвязный планарный граф, не являющийся графом-вершиной, графом-звеном или циклом. Тогда на О есть одна и толко одна планарная сеть. Членами этой планарной сети являются периферические циклы графа О. [48]
Свойство двусвязности, или неразделимости, представляет особый интерес в связи с исследованием пленарных графов. Если связный граф изображен на двумерной сфере, то точки сферы, не принадлежащие нарисованному графу, распадаются на конечное число топологических дисков. В случае когда граф двусвязен, каждый из этих дисков ограничен некоторым циклом графа. Это предложение является топологической теоремой, а соответствующий ему комбинаторный результат приведен в гл. [49]
Рассмотрим конечный автомат А, содержащий г регистров сдвига с линейными или нелинейными обратными связями. Движением регистров управляет специальный блок, который по набору текущих состояний регистров определяет на сколько шагов должен продвинуться ( в смысле движения текущего состояния по циклу внутренних состояний) каждый из регистров за один такт. Особый интерес представляют точки, лежащие на циклах графа этого отображения ( циклические точки) и точки, лежащие на подходах недалеко от циклов. В семидесятые годы А. П. Алферовым и Г. В. Проскуриным для изучения свойств автоматов с неравномерным движением была предложена естественная вероятностная модель таких автоматов. [50]
Ясно, что подграф графа G, содержащий остов Т и его произвольную хорду, имеет только один ( простой) цикл. Множество Z ( T) всех таких циклов ( каждая хорда порождает один цикл) независимо, так как каждый из них содержит ребро, не принадлежащее ни одному из остальных циклов. Более того, любой цикл Z зависит от множества Z ( T), причем Z есть симметрическая разность циклов, которые определяются хордами остова Т, принадлежащими Z. Поэтому, определяя циклический ранг m ( G) как число простых циклов базиса пространства циклов графа G, можно сформулировать следующий результат. [51]
Рассмотрим теперь граф Gn T и пометим циклы графа следующим образом. Напомним, что Мпт - это множество всех графов с п занумерованными вершинами и Т ребрами, компонентами которых являются деревья и компоненты с одним циклом, причем допускаются циклы длины единица и два. Если реализация графа Gn T принадлежит множеству s & n T -, то каждый цикл длины г получает метку с вероятностью рг независимо от остальных циклов. Если граф содержит компоненту с более, чем одним, циклом, то ни один из циклов графа не получает метки. [52]