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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

Орг раф на зы ва ет ся силь но связ ным, ес ли для лю бых двух его вер -
шин w,v су ще ст ву ет путь, со еди няю щий v и w.
Орг раф на зы ва ет ся од но сто рон не связ ным, ес ли для лю бых двух
его вер шин по край ней ме ре од на дос ти жи ма из другой.
Псев до гра фом, ас со ции ро ван ным с ори ен ти ро ван ным псев до гра -
фом D, на зы ва ет ся псев до граф G, в ко то ром X
0
по лу ча ет ся из X за ме ной
всех упо ря до чен ных пар v,w на не упо ря до чен ные v,w (рисунок 1.4.11).
Орг раф на зы ва ет ся сла бо связ ным, ес ли связ ным яв ля ет ся ас со -
ции ро ван ный с ним псевдограф.
Ес ли орг раф не яв ля ет ся сла бо связ ным, то он на зы ва ет ся не -
связ ным.
Ком по нен той связ но сти орг ра фа D на зы ва ет ся его сла бо связ ный
подграф.
Все то же вер но и для не ори ен ти ро ван ных гра фов.
Про стой граф — про сто связ ный.
9) Мат ри цей дос ти жи мо сти орг ра фа D на зы ва ет ся квад рат ная
мат ри ца T(D ) = ||t
ij
|| по ряд ка n, у ко то рой t
ij
= 1, ес ли вер ши на v
j
дос ти жи -
ма из v
i
и t
ij
= 0 — в про тив ном слу чае.
Мат ри цей связ но сти орг ра фа D на зы ва ет ся квад рат ная матрица
S(D) = ||s
ij
|| по ряд ка n, у ко то рой s
ij
= 1, ес ли вер ши на v
i
дос ти жи ма
из v
j
и од но вре мен но v
j
дос ти жи мо из v
i
, и s
ij
= 0 — в про тив ном слу чае.
Ана ло гич но вво дят ся по ня тия со от вет ст вую щих мат риц для гра фа.
За да ния для са мо стоя тель ной ра бо ты:
1) Ка кие час ти го ро да Ке нигс бер га на до со еди нить мос та ми, что -
бы за да ча Эй ле ра име ла по ло жи тель ное решение.
Дос та точ но ли для это го од но го мос та?
24
орг ра ф ас со ции ро ван ный граф
Рис. 1.4.11
      Орграф называется сильно связным, если для любых двух его вер-
шин w,v существует путь, соединяющий v и w.
      Орграф называется односторонне связным, если для любых двух
его вершин по крайней мере одна достижима из другой.
      Псевдографом, ассоциированным с ориентированным псевдогра-
фом D, называется псевдограф G, в котором X0 получается из X заменой
всех упорядоченных пар v,w на неупорядоченные v,w (рисунок 1.4.11).




            орграф                                ассоциированный граф
                                  Рис. 1.4.11


      Орграф называется слабо связным, если связным является ассо-
циированный с ним псевдограф.
      Если орграф не является слабо связным, то он называется не-
связным.
      Компонентой связности орграфа D называется его слабо связный
подграф.
      Все то же верно и для неориентированных графов.
      Простой граф — просто связный.

       9) Матрицей достижимости орграфа D называется квадратная
матрица T(D) = ||tij|| порядка n, у которой tij = 1, если вершина vj достижи-
ма из vi и tij = 0 — в противном случае.
       Матрицей связности орграфа D называется квадратная матрица
       S(D) = ||sij|| порядка n, у которой sij = 1, если вершина vi достижима
из vj и одновременно vj достижимо из vi, и sij = 0 — в противном случае.
       Аналогично вводятся понятия соответствующих матриц для графа.

      Задания для самостоятельной работы:
      1) Какие части города Кенигсберга надо соединить мостами, что-
бы задача Эйлера имела положительное решение.
      Достаточно ли для этого одного моста?
24

Страницы