![]() Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
![]() Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
![]() |
Матрицы графовСтр 1 из 3Следующая ⇒
Методические указания к проведению лекционного занятия Тема № 9.8. Элементы теории графов План: 1. Основные понятия и определения 2. Матрицы графов 3. Достижимость и связность 4. Эйлеровы и гамильтоновы графы. 5. Деревья и циклы
Основные понятия и определения Определение. Если на плоскости задать конечное множество V точек и конечный набор линий Х, соединяющих некоторые пары из точек V, то полученная совокупность точек и линий будет называться графом. При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами. В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями. Одинаковые пары в множестве Х называются кратными (или параллельными) ребрами. Количество одинаковых пар (v, w) в Х называется кратностью ребра (v, w). Множество V и набор Х определяют граф с кратными ребрами – псевдограф. G = (V, X)
Псевдограф без петель называется мультиграфом. Если в наборе Х ни одна пара не встречается более одного раза, то мультиграф называется графом. Если пары в наборе Х являются упорядочными, то граф называется ориентированным или орграфом. Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины.
Определение. Если х = { v, w } – ребро графа, то вершины v, w называются концами ребра х. Если х = (v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х.
Определение. Вершины v, w графа G = (V, X) называются смежными, если { v,w }ÎX. Два ребра называются смежными, если они имеют общюю вершину.
Определение. Степенью вершины графа называется число ребер, которым эта вершина принадлежит. Вершина называется изолированной, если если ее степень равна единице и висячей, если ее степень равна нулю.
Определение.Графы G1(V1, X1) и G2(V2, X2) называются изоморфмными, если существует взаимно однозначное отображение j: V1 ® V2, сохраняющее смежность.
Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v1x1v2x2v3…xkvk+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути).
Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.
Определение. Замкнутый маршрут (путь) называется циклом(контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.
Матрицы графов
Пусть D = (V, X) – орграф, где V = {v1, …, vn}, X = {x1, …, xm}.
Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [aij] порядка п, у которой
Определение. Если вершина v является концом ребра х, то говорят, что v и х – инцидентны.
Определение. Матрицей инцидентности орграфа D называется матрица размерности п ´ т B(D) = [bij], у которой
Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.
x1 v1 x4 v2
x2 x3 v3
Составим матрицу смежности:
Т.е.
Матрица инциндентности:
Т.е.
Если граф имеет кратные дуги (ребра), то в матрице смежности принимается aij=k, где k – кратность дуги (ребра).
С помощью матриц смежности и инциндентности всегда можно полностью определеить граф и все его компоненты. Такой метод задания графов очень удобен для обработки данных на ЭВМ.
Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инциндентности R графа G. Нарисованть также орграф
x3
v2 x2 x5 x6 x1 v1 v3 x7 x8
x10 x11 x9
v4
Составим матрицу инциндентности:
Итого:
Построим теперь ориентированный граф с заданной матрицей смежности.
x5
х9 х17 х15 x14 x16 х13 x12
v4
Составим матрицу инциндентности для ориетированного графа.
Элемент матрицы равен 1, если точка является концом дуги, -1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.
Таким образом, операции с графами можно свести к операциям с их матрицами.
Date: 2015-09-20; view: 2650; Нарушение авторских прав |