Cтраница 3
Неорграф без циклов называется ациклическим. Минимальная из длин циклов неорграфа называется его обхватом. [31]
Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф G называется связным, если соответствующий ему неорграф F ( G) тоже является связным. Граф G называется сильно связным, если для каждой пары различных вершин а и 6 существуют ( а, Ь) - маршрут и ( Ь, а) - маршрут. Аналогично определяются понятия связности и сильной связности для мультиграфов. [32]
Заметим теперь, что если заданный неорграф Г ( т, п, S) не является связным, то в описанном процессе при некотором vm - 1 для соответствующего множества Мч не найдется интересующего нас ребра sv i, одна из вершин которого принадлежит множеству Mv, а другая ему не принадлежит. Следовательно, описанный процесс может использоваться также для определения того, является ли рассматриваемый неорграф связным или нет. [33]
Матрица С называется матрицей связности, если G - неорграф, и матрицей достижимости, если G - орграф. Таким образом, в матрице С содержится информация о существовании связей между различными элементами графа посредством маршрутов. Если G - связный неорграф, то все элементы матрицы связности С равны единице. В общем случае матрица связности неорграфа является матрицей отношения эквивалентности, соответствующего разбиению множества вершин графа на компоненты связности. [34]
Матрица С называется матрицей связности, если G - неорграф, и матрицей достижимости, если G - орграф. Таким образом, в матрице С содержится информация о существовании связей между различными элементами графа посредством маршрутов. Если G - связный неорграф, то все элементы матрицы связности С равны единице. В общем случае матрица связности неорграфа является матрицей отношения эквивалентности, соответствующего разбиению множества вершин графа на компоненты связности. [35]
Но тогда в виде линейной комбинации этих векторов представим также любой вектор а из выделенного ( т - 1) - мерного подпространства EczRm. Следовательно, среди указанных векторов найдутся т - 1 линейно независимых. Отвечающие им ребра в силу доказанной части теоремы образуют покрывающее дерево. Отсюда на основании замечания 6.1 следует, что неорграф Г ( т, N, S) других ребер не содержит и, следовательно, множество N удовлетворяет требуемым условиям. Это завершает доказательство второй части теоремы. [36]