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

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

Степень или валентность вершины графа — количество рёбер графа G, инцидентных вершине v. При подсчёте степени ребро-петля учитывается дважды. Степень вершины обычно обозначается как d(vn) или deg(vn).

Маршрут в графе G = (V,E) есть чередующаяся последовательность вершин и ребер

v0,e1,v1,e2,v2,e3,v3,e4,…,v(n) графа G, для которой каждое ребро инцидентно двум соседним вершинам. При этом v0 есть начало маршрута, v(n) конец маршрута,

---

n длина маршрута.

Цепь в графе G есть маршрут, в котором все ребра попарно различны (нет повторов ребер, возможны повторы вершин).

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

Простой цикл не имеет повторов вершин (кроме начальной и конечной), а, следовательно, и повторов ребер.

Матрица смежности (соседства) вершин (p, q) - графа G=(V, E) с p вершинами есть квадратная

симметричная p x p – матрица. Всякому графу соответствует его бинарная симметричная матрица смежности. Всякой бинарной симметричной квадратной матрице с нулевой диагональю соответствует некоторый граф.

Матрица инциденций (p, q) - графа G c p вершинами и q ребрами есть p x qматрица. Для всякого графа можно построить соответствующую ему бинарную матрицу инциденций. Всякой бинарной матрице с двумя единицами в каждом столбце соответствует некоторый граф.

Ориентированный граф - граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами

G= (V,E) = (V={1,2,3,4,5,6}, E={(1,2),(1,3),(1,5), (1,6),(2,4),(3,4),(3,5),

(3,6), (4,5), (4,6), (5,6)}).

---

Смотрите также файлы

• Самостоятельная работа Обучающийся Копейка Светлана Владимировна Преподаватель Харланова Юлия Викторовна.docx

• Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования новосибирский государственный педагогический университет.rtf

• Занятие 2 по теме Морфологическая стилистика. Стилистическая характеристика частей речи.pdf

• Курсовая работа на тему Верования народов древнего Китая.doc

• Практическое задание 1 задание Выделить роль и место экономической безопасности в системе категорий национальной безопасности. Ответ.docx