Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 15 стр.

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

1) Граф со дер жит два мно же ст ва: мно же ст во V — эле мен та ми ко то -
ро го яв ля ют ся вер ши ны: V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
, v
7
} и мно же ст во X — эле мен -
та ми ко то ро го яв ля ют ся реб ра: X = {x
1
, x
2
, x
3
, x
4
, x
5
, x
6
, x
7
, x
8
, x
9
, x
10
, x
11
, x
12
}
(ри су нок 1.4.1).
2) Вер ши ны v
i
и v
j
, оп ре де ляю щие реб ро x
k
, на зы ва ют ся его кон це -
вы ми вер ши на ми. В этом слу чае реб ро обо зна ча ет ся x
k
= (v
i
, v
j
). Ес ли вер -
ши ны сов па да ют x
k
= (v
i
, v
i
), то та кое реб ро на зы ва ет ся пет лей (ри су -
нок 1.4.2).
Ес ли реб ра гра фа оп ре де ля ют ся упо ря до чен ны ми па ра ми вер -
шин, то граф на зы ва ет ся на прав лен ным или ори ен ти ро ван ным или орг ра -
фом (D). Реб ра орг ра фа на зы ва ют ся ду га ми (ри су нок 1.4.3).
Ес ли па ры яв ля ют ся не упо ря до чен ны ми, то граф на зы ва ет ся не -
ори ен ти ро ван ным или про сто гра фом (G). Оди на ко вые па ры в X на зы ва -
ют ся крат ны ми (или па рал лель ны ми) реб ра ми. Ко ли че ст во оди на ко вых
пар (v,w) в X на зы ва ют ся крат но стью реб ра (v,w).
3) Граф с крат ны ми реб ра ми и пет ля ми на зы ва ет ся псев до гра фом.
Граф на зы ва ет ся про стым, ес ли он не со дер жит пе тель и па рал лель ных
ре бер. Псев до граф без пе тель на зы ва ет ся гра фом с крат ны ми реб ра ми
(или муль ти гра фом). Граф G яв ля ет ся гра фом по ряд ка n, ес ли мно же ст -
во его вер шин со сто ит из n эле мен тов. Граф, не имею щий ре бер на зы ва -
ет ся пус тым. Граф, не имею щий вер шин (и, сле до ва тель но, ре бер) на -
зы ва ет ся нуль-гра фом.
4) Вер ши ны изо бра жа ют кру жоч ка ми, а реб ра — ли ния ми, со еди -
няю щи ми со от вет ст вую щие вер ши ны.
15
Рис. 1.4.2
Рис. 1.4.3
      1) Граф содержит два множества: множество V — элементами кото-
рого являются вершины: V = {v1, v2, v3, v4, v5, v6, v7} и множество X — элемен-
тами которого являются ребра: X = {x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12}
(рисунок 1.4.1).

      2) Вершины vi и vj, определяющие ребро xk, называются его конце-
выми вершинами. В этом случае ребро обозначается xk = (vi, vj). Если вер-
шины совпадают xk = (vi, vi), то такое ребро называется петлей (рису-
нок 1.4.2).




                                      Рис. 1.4.2

     Если ребра графа определяются упорядоченными парами вер-
шин, то граф называется направленным или ориентированным или оргра-
фом (D). Ребра орграфа называются дугами (рисунок 1.4.3).




                                      Рис. 1.4.3

      Если пары являются неупорядоченными, то граф называется не-
ориентированным или просто графом (G). Одинаковые пары в X называ-
ются кратными (или параллельными) ребрами. Количество одинаковых
пар (v,w) в X называются кратностью ребра (v,w).

      3) Граф с кратными ребрами и петлями называется псевдографом.
Граф называется простым, если он не содержит петель и параллельных
ребер. Псевдограф без петель называется графом с кратными ребрами
(или мультиграфом). Граф G является графом порядка n, если множест-
во его вершин состоит из n элементов. Граф, не имеющий ребер называ-
ется пустым. Граф, не имеющий вершин (и, следовательно, ребер) на-
зывается нуль-графом.

    4) Вершины изображают кружочками, а ребра — линиями, соеди-
няющими соответствующие вершины.
                                                                                  15

Страницы