Теоретический материал. Объединением двух, или более графов называется граф, у которого множество вершин и множество дуг объединены (рис
Объединением двух, или более графов называется граф, у которого множество вершин и множество дуг объединены (рис. 1).
Суммой графов 
и 
называется граф, определяемый как объединение графов, причем каждая вершина, не вошедшая в объединение, соединяется с другими вершинами (рис. 2).
Произведением двух графов называется граф, каждая вершина которого представляет собой бинарное отношение (рис. 3).
 |
Матрицей смежности ребер графа называется такая матрица 
, что 
.
Пусть 
- дуги, а 
- вершины ориентированного графа 
.
Матрица 
, такая что 
называется матрицей инциденций для дуг графа.
Матрица 
размером 
, где 
называется матрицей инциденций для ребер графа.
Пример
Для графа изображенного на рисунке 4 найти: 1) матрицу смежности (вершин); 2) матрицу инциденций; 3) матрицу отклонений; 4) вектор отклоненностей; 5) радиус, диаметр, центр и периферийные вершины.
В качестве примера рассмотрим схему первой (1870г.) сети связи для почтовых голубей (рис. 4).
Для построенного графа найдем:
1. матрицу смежности (вершин)
2. матрицу инциденций для дуг и для ребер
3. матрицу отклонений
| Города | П | Б | Л | Г | М | Н |
| Париж | ||||||
| Бордо | ||||||
| Лион | ||||||
| Гренобль | ∞ | ∞ | ∞ | ∞ | ∞ | |
| Марсель | ||||||
| Ницца | ∞ | ∞ | ∞ | ∞ | ∞ |
4. вектор отклоненностей
| Города | П | Б | Л | Г | М | Н |
| ∞ | ∞ |
5. радиус, диаметр, центр, периферийные вершины
диаметр: ∞
центр: 2 (Париж, Лион)
периферийные вершины: Гренобль, Ницца.