9-

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Деревья

Определение. Связный лес называется деревом.

Теорема 6. Пусть в связном графе G = (V ; E) имеется ровно n вершин и m ребер. Тогда следующие условия эквивалентны:

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Деревья

Определение. Связный лес называется деревом.

Теорема 6. Пусть в связном графе G = (V ; E) имеется ровно n вершин и m ребер. Тогда следующие условия эквивалентны:

I G дерево;

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Деревья

Определение. Связный лес называется деревом.

Теорема 6. Пусть в связном графе G = (V ; E) имеется ровно n вершин и m ребер. Тогда следующие условия эквивалентны:

IG дерево;

Iкаждое ребро из G мост.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Деревья

Определение. Связный лес называется деревом.

Теорема 6. Пусть в связном графе G = (V ; E) имеется ровно n вершин и m ребер. Тогда следующие условия эквивалентны:

IG дерево;

Iкаждое ребро из G мост.

Iкаждая цепь, соединяющая две вершины, единственна;

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Деревья

Определение. Связный лес называется деревом.

Теорема 6. Пусть в связном графе G = (V ; E) имеется ровно n вершин и m ребер. Тогда следующие условия эквивалентны:

IG дерево;

Iкаждое ребро из G мост.

Iкаждая цепь, соединяющая две вершины, единственна;

Im+1=n;

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Эйлеровы и гамильтоновы пути

Определение. Пусть дан граф G = (V ; E; ) и количество ребер равно m . Эйлеровым путем называется замкнутый путь длины m состоящий из различных ребер без повторений.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Эйлеровы и гамильтоновы пути

Определение. Пусть дан граф G = (V ; E; ) и количество ребер равно m . Эйлеровым путем называется замкнутый путь длины m состоящий из различных ребер без повторений. Если условие замкнутости убрать, то получим определение полуэйлерового пути.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Эйлеровы и гамильтоновы пути

Определение. Пусть дан граф G = (V ; E; ) и количество ребер равно m . Эйлеровым путем называется замкнутый путь длины m состоящий из различных ребер без повторений. Если условие замкнутости убрать, то получим определение полуэйлерового пути.

Определение. Пусть дан граф G = (V ; E; ) и количество вершин равно n . Гамильтоновым путем называется замкнутая цепь длины n.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Эйлеровы и гамильтоновы пути

Определение. Пусть дан граф G = (V ; E; ) и количество ребер равно m . Эйлеровым путем называется замкнутый путь длины m состоящий из различных ребер без повторений. Если условие замкнутости убрать, то получим определение полуэйлерового пути.

Определение. Пусть дан граф G = (V ; E; ) и количество вершин равно n . Гамильтоновым путем называется замкнутая цепь длины n. Если условие замкнутости убрать, то получим определение полугамильтонового пути.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Критерий эйлеровости и полуэйлеровости

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