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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

52
Неограф называется связным, если между любыми его вершинами
есть маршрут. При этом две вершины являются связными, если между
ними существует маршрут.
Ребро связного графа является мостом , если после его удаления граф
становится несвязным и распадается на два связных графа.
При графовом задании бинарного отношения рефлексивность для
каждой вершины представляется петлей (рис.6.9,а). Следствием
симметричности является наличие между всякой парой вершин двух
противоположно направленных дуг (рис.6.9,б), а при транзитивности для
всякой пары дуг, таких, что конец первой совпадает с началом второй ,
существует третья дуга, имеющая общее начало с первой и общий конец со
второй (рис.6.9,в).
а) б) в)
Рис.6.9. Графы элементов рефлексивных (а), симметричных (б) и
транзитивных (в) бинарных отношений .
Задания
6.23. Изобразить граф
RMG ; =
, заданный множествами
M
и R:
а)
{
}
dcbaM ,,,=
и
(
)
(
)
(
)
(
)
(
)
(
)
{
}
adcddccbbaaaR ,,,,,,,,,,,=
;
б)
{
}
cbaM ,,
=
и
[
]
[
]
[
]
(
)
{
}
cacbbbbaR ,,,, UUU
=
;
в)
{
}
4,3,2,1=M
и
[
]
[
]
(
)
(
)
(
)
(
)
{
}
1,4,2,3,4,2,3,14,32,1 UU = R
;
6.24. В аналитической форме представить графы, изображенные ниже:
Какой из графов является связным? Какие из данных графов
являются ориентированными?
2
●
●
1
а )
●
●
3
4
●
●
●
●
●
a
1
a
2
a
3
a
4
a
5
б)
1
2
●
в )
●
●
3
1
2
●
г)
●
●
3
●
4
2
●
●
1
д)
●
●
3
4
•
•
m
j
m
i
m
k
•
•
•
m
j
m
i
•
m
i 
                                                 52
    Неограф называется связным, если между любыми его вершинами
есть маршрут. При этом две вершины являются связными, если между
ними существует маршрут.
    Ребро связного графа является мостом, если после его удаления граф
становится несвязным и распадается на два связных графа.
    При графовом задании бинарного отношения рефлексивность для
каждой вершины представляется петлей (рис.6.9,а). Следствием
симметричности является наличие между всякой парой вершин двух
противоположно направленных дуг (рис.6.9,б), а при транзитивности для
всякой пары дуг, таких, что конец первой совпадает с началом второй,
существует третья дуга, имеющая общее начало с первой и общий конец со
второй (рис.6.9,в).            m            i            • mk
                                             •               mj
                                                                  •
                   mi •                                               mi •
                              а)
                                          mj •
                                            б)                        в)

      Рис.6.9. Графы элементов рефлексивных (а), симметричных (б) и
                   транзитивных (в) бинарных отношений.
                                        Задания
6.23. Изобразить граф G = M ; R ,заданный множествами M и R:
     а) M ={a, b, c, d } и R ={(a, a ), (a, b ), (b, c ), (c, d ), (d , c ), (d , a )};
     б) M ={a, b, c} и R =[a, b] [b, b] [b, c ] {(a, c )};
     в) M ={1, 2, 3, 4} и R =[1, 2] [3, 4] {(1, 3), (2, 4 ), (3, 2 ), (4, 1)};
6.24. В аналитической форме представить графы, изображенные ниже:
           2●                      a2 ●           a3 ●                               2
                                                                                     ●

 1●                       3
                      ●

                                   a1 ●           a4●         ●
                                                             a5
                                                                           1●            ●3
           4●
                                                  б)                            в)
            а)                              2●
      2           3           4
       ●          ●           ●
                                                         3
                                    1●                   ●

           ●
           1                                4●
           г)                                д)
     Какой из графов является связным? Какие из данных графов
являются ориентированными?

Страницы