Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 8 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

10
1. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
1.1. Основные понятия и определения
Теория графов, как и любая математическая теория, использует
некоторую символику и понятия, которые применяются при проведении
исследований. Центральным понятием теории графов является понятие
графа, как некоторой схемы, состоящей из множества
{
}
n
j
AA = вершин
(узлов), соединённых между собой множеством
{
}
m
jiM ),(
=
некоторых
линий (дуг ),(
j
i ) [1; 2]. Граф ),(
M
A
G
=
– это схематическое изображение
некоторого физического объекта (участка дорожной сети, электросхемы и
т.п.). С формальных позиций, граф – это отображение множества
A
«в себя» (т.е. в множество
A
), осуществляемое по некоторому закону
Γ
(с
помощью множества дуг
M
). Граф дорожной сети или, например, сети
передачи данных представлен на рис. 1. В первом случае под вершиной
i
A
имеется в виду некий населенный пункт (город, деревня под номером
i ),
во втором – некий узел связи (
узел коммутации – УК, узел-источник – УИ
i
A , узел-приёмник – УП
j
A ).
Две вершины, связанные одной дугой ),(
j
i , называются смежными.
При этом начало дуги связано с источником
i
A , а её конец – с приёмником
j
A . В зависимости от физической природы графа каждой его дуге
приписывается некоторый вес
ij
c : в первом случае это длина дуги ),(
j
i ,
связывающей вершину
i
A
с
j
A ; во втором – длительность передачи
сигнала от узла-источника
i
A до узла-приёмника
j
A . Направление, по
которому возможно движение (передача сигнала) по данной дуге,
указывается стрелкой (см. рис. 1).
Граф с направленными дугами называется
ориентированным. В
неориентированном графе стрелки не указываются (ребро – пара дуг
jiij
cс = ).
Для проведения формальных исследований удобна матричная форма
представления графа с помощью матрицы
смежности. Её смысл ясен из
матрицы
ij
c=c , представляющей тот же граф в табличном виде (табл. 1).
Каждая вершина графа представляется в виде двух составляющих:
узла-источника
i
A и узла-приёмника
j
A , при этом узлу-источнику
i
A
соответствует
i
-я строка матрицы c, узлу-приёмнику
j
A –
j
-й столбец
этой же матрицы (табл. 1).
Согласно [1],
путём (маршрутом) на графе ),(
M
A
G
=
будем называть
такую последовательность соединённых дуг ),(
j
i , что конец каждой

Страницы