Неориентированный граф

Cтраница 2

Неориентированным графом называется множество как угодно размещенных на плоскости, точек, некоторые из которых соединены линиями любой формы. Два неориентированных графа считаются неразличимыми, если они отличаются друг от друга только формой соединительных линий или способом размещения точек на плоскости. [16]

Неориентированным графом пли просто графом G ( X, U) называется упорядоченная пара - ( X, U), где X есть множество вершин графа, a U есть множество неупорядоченных пар элементов из X, называемых ребрами графа. [17]

Абсолютный центр. [18]

Рассмотрим неориентированный граф О, показанный на рис. 5.3, где все веса вершин и длины ребер равны единице. [19]

Связный неориентированный граф, не содержащий циклов, называется деревом. В частности, дерево не имеет петель и кратных ребер. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов. В дереве любые две вершины связаны единственной цепью. Величина дерева равна произведению величины его ребер. [20]

Дан неориентированный граф Г ( V, Е) без кратных ребер и петель, причем V v, E e, и натуральное число г / о. Вершины графа размещаются в целых точках интервала 10, v - 1 ] числовой прямой. Под длиной ребра ( i, ; ) Е при данном размещении понимается число х ( - х, где х и х - координаты точек, в которых размещены вершины in / графа Г соответственно. [21]

Каждый неориентированный граф распадается единственным образом в прямую сумму ( 2.2 2) своих связных компонент. [22]

Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево но имеет петель п ратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов. [23]

Любой неориентированный граф без изолированных вершин имеет такое доминирующее множество D, что его дополнение D также является доминирующим множеством. [24]

Связанный неориентированный граф называется деревом, если он не имеет циклов. [25]

Связный неориентированный граф содержит эйлеров цикл тогда и только тогда, когда степень каждой вершины четна. [26]

Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево не имеет петель и кратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов. [27]

Дан неориентированный граф F ( F, E) и натуральное число уй. [28]

Абсолютный центр. [29]

Рассмотрим неориентированный граф G, показанный на рис. 5.3, где все веса вершин и длины ребер равны единице. [30]

Страницы: 1 2 3 4