Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
E)Построение матрицы инциденций.
|
|
Матрица инциденций графа G 1 представляет собой прямоугольную матрицу 
размером 5´ 9, где 5 – количество вершин графа, а 9 – количество дуг графа.
| bij = 1, если xi является начальной вершиной дуги aj, bij = -1, если xi является конечной вершиной дуги aj, bij = 0, если xi не является концевой вершиной дуги aj или если aj является петлей. |
|
F)Построениесписка концов ребер.
Для каждого ребра задается пара инцидентных ему вершин. В случае орграфа первой указывается начальная вершина.
| a 1 | a 2 | a 3 | a 4 | a 5 | a 6 | a 7 | a 8 | a 9 |
| x 1 | x 1 | x 1 | x 2 | x 2 | x 3 | x 4 | x 4 | x 5 |
| x 3 | х 4 | x 5 | x 1 | x 2 | x 4 | x 1 | x 3 | x 4 |
Задание 2. Бинарные операции над графами.
Дано: матрицы смежности орграфов G 1 и G 2:
|
|
Необходимо для орграфа G 1 выполнить бинарные операции матричным способом:
A) объединения; пересечения; разности; кольцевой суммы.
Решение.
Объединение: G = G 1 È G 2 = (X 1 È X 2, A 1 È A 2).
Пересечение: G = G 1 Ç G 2 = (X 1 Ç X 2, A 1 Ç A 2).
Разность: G = G 1 \ G 2 = (X 1 \ X 2, A 1 \ A 2).
Кольцевая сумма: Граф G = (X, A) = G 1 Å G 2, порожден на множестве ребер А 1 Å А 2.
Другими словами, граф G = (X, A) не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G 1, либо в G 2, но не в обоих одновременно.
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| G = G 1 È G 2 | G = G 1 Ç G 2 | G = G 1 \ G 2 | G = G 1 Å G 2 |