Многообразие схем

Информационные модели на графах

Графом называется конечное множество точек, некоторые из которых соединены линиями.

Наглядным средством представления состава и структуры системы является граф.

Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер.

Multiple Choice

Все ли точки графа должны быть соединены линиями?

• Да, обязательно все

• Нет, могут быть соединены только некоторые

• Соединений может не быть вообще

Точки называются вершинами графа, а соединяющие линии — рёбрами.

Количество рёбер, выходящих из вершины графа, называется степенью вершины. 

Изолированная вершина — вершина, степень которой равна 0

Конечная вершина графа — вершина, степень которой равна 1

Направленная линия (со стрелкой) называется дугой

Линия ненаправленная (без стрелки) называется ребром

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлёй

Multiple Select

Какие существуют виды соединений вершин графа?

• Пунктир

• Ребро

• Дуга

• Петля

Виды графов

• Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).

• Граф называется неориентированным, если его вершины соединены рёбрами.

• Цепь — путь по вершинам и рёбрам, включающий любое ребро графа не более одного раза.

• Цикл — цепь, начальная и конечная вершины которой совпадают.

• Граф с циклом называют сетью.

• Ориентированный граф — граф, рёбрам которого присвоено направление.

Multiple Select

Какие из видов графов зависят от наличия направления у рёбер?

• Взвешенный граф

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

• Сеть

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