Задача 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