Cтраница 1
Неорграф Г ( т, п, S) в том и только том случае не содержит циклов, если столбцы соответствующей матрицы (6.7) линейно независимы. [1]
Неорграф без петель называется полным, если его любые две различные вершины смежны. [2]
Неорграф без циклов называется ациклическим. Минимальная из длин циклов неорграфа называется его обхватом. [3]
Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф G называется связным, если соответствующий ему неорграф F ( G) тоже является связным. Граф G называется сильно связным, если для каждой пары различных вершин а и 6 существуют ( а, Ь) - маршрут и ( Ь, а) - маршрут. Аналогично определяются понятия связности и сильной связности для мультиграфов. [4]
Неорграф Г ( М, N, S) называется связным, если для любых двух различных вершин / и / этого графа имеется, по крайней мере, одна связывающая их цепь. [5]
Неорграф Г ( М, N, S) называется деревом, если он является связным и не содержит циклов. [6]
Неорграф G называется планарным, если его можно изобразить на плоскости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости называется плоским. [7]
Поэтому неорграф Г ( М, N, S) часто отождествляется со своим графическим изображением. [8]
Этот неорграф имеет р2 связных компонент. [9]
Тогда рассматриваемый неорграф является связным. [10]
Не всякий неорграф является планарным. [11]
Деревом называется связный неорграф, не содержаций циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом компонентами связности любого леса являются деревья. [12]
Теорема 4.12.3. В связном неорграфе любой цикл имеет с любым разрезом четное, число общих ребер. [13]
Теорема 4.12.1. В конечном неорграфе G ( M R), имеющем с компонент связности, множество ребер К тогда и только тогда является коциклом, когда граф ( М, R К) имеет ( с 1) компонент связности. [14]
Нетрудно проверить, что неорграф Г ( М, N, S) в том и только том случае содержит цикл длины / 1, если для некоторых двух различных вершин этого неорграфа имеется более одной связывающей их цепи. [15]