Cтраница 2
Заметим теперь, что если заданный неорграф Г ( т, п, S) не является связным, то в описанном процессе при некотором vm - 1 для соответствующего множества Мч не найдется интересующего нас ребра sv i, одна из вершин которого принадлежит множеству Mv, а другая ему не принадлежит. Следовательно, описанный процесс может использоваться также для определения того, является ли рассматриваемый неорграф связным или нет. [16]
Но тогда на основании леммы 6.2 неорграф Г ( т, N, S) будет связным и потому является покрывающим деревом. [17]
Пусть G ( M R) - неорграф, имеющий п вершин, т, ребер и с компонент связности, Т - остов графа G. В § 4.8 отмечалось, что Т имеет v ( G ] п - с ребер и... Vi, то в полученном графе найдется ровно один цикл, который обозначим через С. Цикл d состоит из хорды Vi и некоторых ветвей остова Т, которые принадлежат единственной простой цепи, соединяющей вершины хорды Vj. [18]
При этом элементы множества М называют вершинами неорграфа Г ( М, N, S), а элементы множества Л7 - его ребрами. [19]
Наконец, учитывая, что для каждого связного неорграфа Г ( М, N, S) имеется покрывающее дерево, с помощью теоремы 6.1, замечания 6.1 и следствия 2 из леммы 6.1 можно проверить справедливость следующих более общих утверждений. [20]
Ясно, что для характеристики того или иного неорграфа существенны не сами множества М и N, a лишь число элементов в каждом из них и закон образования соответствующих неупорядоченных пар. [21]
Пусть G ( М, R) - связный неорграф, имеющий п вершин и т ребер ui, U2, -, ит. [22]
Матрица С называется матрицей связности, если G - неорграф, и матрицей достижимости, если G - орграф. Таким образом, в матрице С содержится информация о существовании связей между различными элементами графа посредством маршрутов. Если G - связный неорграф, то все элементы матрицы связности С равны единице. В общем случае матрица связности неорграфа является матрицей отношения эквивалентности, соответствующего разбиению множества вершин графа на компоненты связности. [23]
Граф G ( X, U), у которого U U, называют неориентированным или неорграфом. [24]
Для орграфов вводятся понятия пути и контура, аналогичные рассмотренным понятиям цепи, и цикла для случая неорграфов. [25]
Если столбцы матрицы (6.7), отвечающей неорграфу Г ( т, п, S), линейно независимы, то этот неорграф не содержит циклов. [26]
Деревом называется связный неорграф, не содержаций циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом компонентами связности любого леса являются деревья. [27]
Предположим вначале, что матрица A ( Sf) удовлетворяет условиям теоремы. Тогда неорграф Г ( т, N, S) в силу следствия 2 из леммы 6.1 не содержит циклов. [28]
Тогда из них можно было бы выбрать вершину с наибольшим номером i0 m - 1, которая не связана ни с одной из вершин с большим номером. Следовательно, неорграф Г ( т, т - 1, S) является связным, что и требовалось показать. [29]
Поэтому многие результаты для неорграфов справедливы и для орграфов. [30]