Неориентированный граф
Cтраница 1
 |
Замкнутый граф. [1] |
Неориентированный граф называется связным, если каждую вершину его можно соединить с любой другой вершиной некоторой цепью. В неориентированном графе цепь является аналогом пути в ориентированном графе. [2]
Неориентированный граф называется полным, если любые две его вершины соединены ребром. [3]
 |
Полные неориентированные графы.| Исходный граф Г и дополнительный Г.| Граф Г - плоский, а граф Г2 - неплоский. [4] |
Неориентированный граф называется простым, если он не имеет петель и любая пара вершин соединена не более чем одним ребром. [5]
Неориентированный граф, который не содержит параллельных ребер и петель; ориентированный граф, который не содержит строго параллельных дуг и петель. [6]
Неориентированный граф состоит из конечного множества вершин и конечного множества ребер, связывающих вершины. Любые две вершины связаны не более чем одним ребром; не должно быть двух дублирующих друг друга ребер; кроме того, для рассматриваемой задачи мы запрещаем ребру связывать вершину с самой собой. На рис. 3.1 изображен неориентированный граф, представляющий первые 49 американских штатов. Ввести граф в ЭВМ несложно: достаточно перечислить все вершины, сопроводив каждую списком смежных ей вершин. Граф может не иметь вершин, а значит, и ребер; такой граф называется пустым. Вершина может быть изолированной, если нет ребер, связывающих ее с другими вершинами ( примером тому могли бы служить Аляска и Гавайи); точно так же две части графа окажутся изолированными друг от друга, если нет ребер, их связывающих. [7]
Неориентированный граф без петель, в котором выделено некоторое подмножество вершин, называется сетью, а выделенные вершины - полюсами сети. [8]
Неориентированный граф ( или просто граф) G состоит из конечного непустого множества V ( G) элементов, называемых вершинами и множества E ( G) неориентированных пар вершин, называемых ребрами. Обратите внимание, что мы допускаем здесь кратные, или параллельные, ребра, если не оговорено обратное. Если кратные ребра не допускаются, мы будем называть такой граф простым. [9]
Неориентированный граф О ( X, А) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Ха и Хь, что каждое ребро имеет один конец в Ха, а другой в Хь. Ориентированный граф С называется двудольным, если его неориентированный двойник О - двудольный граф. Легко доказать следующее утверждение. [10]
Неориентированный граф С является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. [11]
Неориентированный граф G ( X, А) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Ха и Хь, что каждое ребро имеет один конец в Ха, а другой в Хь. Ориентированный граф G называется двудольным, если его неориентированный двойник G - двудольный граф. Легко доказать следующее утверждение. [12]
Неориентированный граф G является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. [13]
Неориентированный граф G связен, если существует хотя бы один путь в G между каждой парой вершин vt и Vj. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Говорят, что ориентированный граф сильно связен, если для каждой пары вершин vt и Vj существует по крайней мере один ориентированный путь из Vi в Vj и по крайней мере один из v в иг. Граф, состоящий из единственной изолированной вершины, является ( тривиально) связным. Максимальный:) связный подграф графа G называется связной компонентой или просто компонентой G. Несвязный граф состоит из двух или более компонент. Максимальный сильно связный подграф называется сильно связной компонентой. [14]
Неориентированному графу G соответствуют 3Г23 различных графов G, где г - число ребер, s - число вершин. [15]
Страницы: 1 2 3 4