Cтраница 4
Эта теорема является основной в теории простых графов. [46]
Одним из наиболее распространенных машинных представлений простого графа является матрица смежностей или соединений. Матрица смежностей графа G ( V, E) есть Vx У - матрица А1ац ], в которой atj-l, если в G существует ребро, идущее из t - й вершины в j - ю, и а - - 0 в противном случае. [47]
Докажите, что сумма характеристических чисел простого графа равна нулю, и проиллюстрируйте это на примере полных графов и полных двудольных графов. [48]
Докажите, что реберные графы эйлерова простого графа и гамильтонова простого графа являются гамильтоновыми. [49]
Логическая матрица отношения на множестве вершин простого графа G, которое задается его ребрами, называется матрицей смежности. [50]
Реберным графом L ( G) простого графа G называется граф, вершины которого взаимно однозначно сопоставлены ребрам графа G, причем две вершины в L ( G) смежны тогда и только тогда, когда соответствующие им ребра смежны в G. [51]
Определим граф С-мостов для графа О как простой граф, вершинами которого являются С-мосты графа Сив котором две вершины соединены ребром тогда и только тогда, когда соответствующие им мосты перекрываются. Тогда имеет место следующее достаточное условие непланарности. [52]