Математика. Быкадорова Г.В. - 50 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

50
При задании графа природа
связи между вершинами не имеет
значения, важно только то, что связь
существует и информация о связях
содержится во множестве R . Однако
часто возникает ситуация, когда такой
информации недостаточно , например, в
случаях , когда имеется несколько дуг,
исходящих из вершины а в вершину b
( рис. 6.6).
Такие дуги называются кратными и для описания таких графов
используется понятие мультиграфа.
Определение . Мультиграфом G называется тройка PUM ,, , в которой М
– множество вершин, U – множество дуг, а MMMP
×
×
⊆
- трехместный
предикат , называемый инцидентором и представляемый как :
(
)
Pbua
∈
,,
тогда и только тогда, когда дуга u исходит из вершины а и заходит в
вершину b .
Граф RMG , = называется ориентированным (орграфом ), если
найдется дуга
(
)
Rba
∈
,
такая, что
(
)
Rab
∉
,
.
Если отношение R симметрично, т.е. из
(
)
Rba
∈
,
следует
(
)
Rab
∈
,
, то
граф G называется неориентированным или неографом .
Если одновременно пары
(
)
ba ,
и
(
)
ab ,
принадлежат R (рис. 6.7,а), то
информацию об этих дугах можно представить множеством
[
]
(
)
(
)
{
}
abbaba ,,,,
=
, называемым ребром , соединяющим вершины а и b. При
этом вершины а и b называются концами ребра
[
]
ba , . Ребра изображаются
линиями без стрелок , соединяющими вершины (рис. 6.7,б).
Если в мультиграфе вместо дуг рассматриваются ребра, то такой
мультиграф также называется неориентированным.
Ребро графа является инцидентным по отношению к вершинам ,
которые оно соединяет. При этом инцидентные ребру вершины
называются смежными (рис.6.8,а). Два ребра являются смежными, если
они имеют общую вершину.
Если начало и конец ребра совпадают, то такое ребро является
петлей (рис.6.5).
●
●
а
b
Рис. 6.6. Изображение
мультиграфа.
●
●
а
b
а) б)
Рис. 6.7. Элемент неографа (а) и ребро
[
]
ba , (б).
●
●
а
b
                                     50
                                                   При задании графа природа
                                         связи между вершинами не имеет
      а                            b     значения, важно только то, что связь
      ●                           ●      существует и информация о связях
                                         содержится во множестве R. Однако
                                         часто возникает ситуация, когда такой
       Рис. 6.6. Изображение             информации недостаточно, например, в
             мультиграфа.                случаях, когда имеется несколько дуг,
                                         исходящих из вершины а в вершину b
                                         (рис. 6.6).
        Такие дуги называются кратными и для описания таких графов
используется понятие мультиграфа.
Определение. Мультиграфом G называется тройка M ,U , P , в которой М
– множество вершин, U – множество дуг, а P ⊆ M ×M ×M - трехместный
предикат, называемый инцидентором и представляемый как: (a, u, b )∈P
тогда и только тогда, когда дуга u исходит из вершины а и заходит в
вершину b.
       Граф G = M , R называется ориентированным (орграфом), если
найдется дуга (a, b )∈R такая, что (b, a )∉R .
       Если отношение R симметрично, т.е. из (a, b )∈R следует (b, a )∈R , то
граф G называется неориентированным или неографом.
       Если одновременно пары (a, b ) и (b, a ) принадлежат R (рис. 6.7,а), то
информацию об этих дугах можно представить множеством
[a, b] ={(a, b), (b, a )}, называемым ребром, соединяющим вершины а и b. При
этом вершины а и b называются концами ребра [a, b]. Ребра изображаются
линиями без стрелок, соединяющими вершины (рис. 6.7,б).

                                                                b
     а                   b            а
      ●                  ●                ●                    ●




                 а)                             б)
          Рис. 6.7. Элемент неографа (а) и ребро [a, b] (б).

     Если в мультиграфе вместо дуг рассматриваются ребра, то такой
мультиграф также называется неориентированным.
     Ребро графа является инцидентным по отношению к вершинам,
которые оно соединяет. При этом инцидентные ребру вершины
называются смежными (рис.6.8,а). Два ребра являются смежными, если
они имеют общую вершину.
     Если начало и конец ребра совпадают, то такое ребро является
петлей (рис.6.5).

Страницы