Математическое моделирование на графах. Часть 1. Берцун В.Н. - 6 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

6 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
соединяющей соответствующие
точки. Получился граф, изображён-
ный на рис. 1.2.
Анализируя этот граф, Эйлер
доказал, что сформулированная
выше задача о мостах не имеет ре-
шения.
Важным стимулом к развитию
теории графов явилась возникшая в
середине XIX в. задача о четырех
красках. Любую карту на плоско-
сти раскрасить в четыре цвета
так, чтобы смежные страны имели различные цвета. Решить эту
задачу удалось только в конце ХХ в. с помощью компьютера [11].
1.2. Граф и его дополнение
Графом G(V, E) называется совокупность двух множеств – непус-
того множества объектов некоторой природы V (вершин графа) и
множества E неупорядоченных пар элементов множества V,
называемых ребрами графа (V ≠ ∅, E ⊆ V × V). Таким образом, граф
определяется множеством вершин V, множеством рёбер E (подмно-
жеством двухэлементных подмножеств множества V) и отношением
инцидентности, которое каждому ребру сопоставляет одну или две
вершины. При изображении графов на рисунках отрезки (ребра)
могут быть криволинейными и прямолинейными, а длины отрезков
и расположение точек произвольно. Будем рассматривать только
такие графы, у которых множества V(G) и E(G) конечны
(n = n(G) =│V│, m = m(G) =│E│) [11 – 16].
Ребро графа называется звеном, если у него два конца, и петлей,
если конец один (петля это ребро, у которого два конца совпадают).
Два или более звеньев, имеющих одинаковые пары концов, образу-
ют кратное соединение и называются кратными рёбрами. Граф без
петель и кратных рёбер называется простым. Примеры графов изо-
бражены на рис. 1.3.
A
C
B
L
Рис. 1.2

Страницы