Cтраница 4
Отправляясь от его формул, сравнительно просто удалось перечислить корневые графы, связные графы и ориентированные графы. [46]
Если 1 ( и) растет слишком медленно, то большинство графов будет иметь много компонент. В этом случае функция Х ( п) в (4.2) не ограничена, и весьма правдоподобно, что число компонент имеет скорее нормальное распределение, чем пуассомовское. Доказательство автору не известно. Рассмотрим случай, когда связные графы составляют разумную часть всех графов. Представим себе граф с v вершинами, и пусть v увеличивается за счет добавления ребер. [47]
Заметим, что нетривиальный граф 1-связен тогда и только тогда, когда он связен, и 2-связен тогда и только тогда, когда он является блоком, имеющим более одного ребра. Таким образом, граф / С2 - единственный блок, не являющийся 2-связным. Из теоремы 3.3 поэтому следует, что граф 2-связен тогда и только тогда, когда каждые две его вершины принадлежат некоторому простому циклу. Дирак [4] распространил это замечание на n - связные графы. [48]
Показать, как можно построить граф 11 0 из / / с минима. В дереве существует единственная кратчайшая простая цепь между любыми двумя вершинами, но существуют и другие связные графы с тем же свойством. [49]
Предположим теперь, что в наборе 5 ( см. ( V. Я / двусвязен и содержит меньше вершин, чем граф О. Предположим далее, что графы Я / удовлетворяют соотношению ( V. Тогда, если К является связным носителем реализации набора 5 в графе О, то он должен быть таким разделимым графом, у которого блоки совпадают, с точностью до изоморфизма, с графами из набора 5 ( см. теорему V. V ( С, К), взятая по всем таким связным графам / С, у которых блоки являются, с точностью до изоморфизма, элементами набора 5, восстанавливаема. Иной путь получения этого результата дает следующее утверждение. [50]
Мы изучали периодические, квазипериодические, ( слабо) псевдопериодические слова. Теперь требуется рассмотреть кусочно периодические слова. Необходимость их изучения вызвана следующими обстоятельствами. Во-первых, по теореме Ширшова о высоте такие слова образуют нормальный базис Pi-алгебры. Во-вторых, понятие кусочной периодичности служит естественным обобщением понятия периодичности. В третьих, типам таких слов соответствуют связные графы без параллельных ребер, и язык типов соответствует языку графов. При изучении кусочной периодичности возникают понятия и леммы, позволяющие дать описание представимых мономи-альных алгебр. Все это составляет также аппарат, необходимый для изучения многообразий мономиальных алгебр. [51]