Введение в теорию графов

Введение в теорию графов 11 класс

Введение в теорию графов

Граф - это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).

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

Нулевой граф

Неполный граф

Степень графа

Задание 1. Существует ли полный граф с семью ребрами?

Задание 2.

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

Задание 3.Построить граф по заданному условию:

Запомнить!

Изображение графа

Задание 4.

Задание 5.

Путь называется простым, если он не проходит ни через одну из вершин графа более одного раза.

Понятие цикла в графе

a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являются простыми?

ОТВЕТ