Основные понятия теории графов. Гладких О.Б - 9 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

168
6. Даны два графа
Произвести непосредственное сложение этих гра-
фов. Составить матрицы смежности и найти с их
помощью пересечение графов.
7. Даны два графа своими матрицами смежности:
Составить матрицу смежности, соответст-
вующую сумме и пересечению графов. Нарисовать
диаграммы исходных и результирующих графов
8. Даны три графа:
9
1B1. Основные характеристики графов
1.1. Виды и способы задания графов
Определение 1.1. Графом G (V, E) называется со-
вокупность двух множеств – непустого множества
V (множества вершин) и множества Е его двухэле-
ментных подмножеств множества V (Е – множест-
во ребер).
G (V, E) = EV ; , V ≠ ∅, E ⊂ 2
V
Определение 1.2. Граф G – это математический
объект, состоящий из множества вершин
X = {x
1
,
x
2
, ..., x
n
} и множества ребер A = {a
1
, a
2
,..., a
n
}. Та-
ким образом, граф полностью определяется сово-
купностью множеств X, A: G
= (X, A).
Определение 1.3. Графом называется алгебраиче-
ская система G = (M; R), где R – двухместный пре-
дикатный символ. Элементы носителя М называ-
ются вершинами графа G, а элементы бинарного
отношения R ³ М
2
– дугами. Таким образом, ду-
гами являются пары вершин (а, b) ´ R. При этом
дуга (а,.b) называется исходящей из вершины а и
заходящей в вершину b.
Для многих задач несущественно, являются
ли ребра отрезками прямых или криволинейными
дугами; важно лишь то, какие вершины соединяет
каждое ребро. 
6. Даны два графа                                      1. Основные характеристики графов
                                                       1B




                                                            1.1. Виды и способы задания графов
                                                 Определение 1.1. Графом G (V, E) называется со-
                                                 вокупность двух множеств – непустого множества
                                                 V (множества вершин) и множества Е его двухэле-
                                                 ментных подмножеств множества V (Е – множест-
                                                 во ребер).
                                                                G (V, E) = V ; E , V ≠ ∅, E ⊂ 2V
Произвести непосредственное сложение этих гра-   Определение 1.2. Граф G – это математический
фов. Составить матрицы смежности и найти с их    объект, состоящий из множества вершин X = {x1,
помощью пересечение графов.                      x2, ..., xn} и множества ребер A = {a1, a2,..., an}. Та-
7. Даны два графа своими матрицами смежности:    ким образом, граф полностью определяется сово-
                                                 купностью множеств X, A: G = (X, A).
                                                 Определение 1.3. Графом называется алгебраиче-
                                                 ская система G = (M; R), где R – двухместный пре-
                                                 дикатный символ. Элементы носителя М называ-
                                                 ются вершинами графа G, а элементы бинарного
      Составить матрицу смежности, соответст-    отношения R ³ М 2 – дугами. Таким образом, ду-
вующую сумме и пересечению графов. Нарисовать    гами являются пары вершин (а, b) ´ R. При этом
диаграммы исходных и результирующих графов       дуга (а,.b) называется исходящей из вершины а и
8. Даны три графа:                               заходящей в вершину b.
                                                          Для многих задач несущественно, являются
                                                 ли ребра отрезками прямых или криволинейными
                                                 дугами; важно лишь то, какие вершины соединяет
                                                 каждое ребро.




                        168                                                    9

Страницы