Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Если , то граф G′ называется собственным подграфом графа G.

Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержит все возможные рёбра G.

Степень (валентность) вершины – это количество ребер, инцидентных этой вершине (количество смежных с ней вершин).

Маршрутом в графе называется чередующаяся последовательность вершин и ребер , в которой любые два соседних элемента инциденты.

Если , то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью.

Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь называется циклом.

Замкнутая простая цепь называется простым циклом.

Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл – контуром.

рис. 4. Маршруты, цепи, циклы

Пример

В графе, диаграмма которого приведена на рис.4:

v1, v3, v1, v4 – маршрут, но не цепь;

v1, v3, v5, v2, v3, v4 – цепь, но не простая цепь;

v1, v4, v3, v2, v5 – простая цепь;

v1, v3, v5, v2, v3, v4, v1 – цикл, но не простой цикл;

v1, v3, v4, v1 – простой цикл.

Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом.

Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом.

Деревом называется связный граф без циклов.

Остовом называется дерево, содержащее все вершины графа.

Паросочетанием называется множество ребер, в котором никакие два не смежны.

Рекомендуем скачать другие рефераты по теме: реферат памятники, бесплатные рефераты без регистрации.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата