Специальная математика. Соловьев А.Е. - 47 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

x
4
x
5
Следует отметить некоторые практические особенности теории графов. Слово граф
однокоренное со словом графика. Поэтому не удивительно, что многие задачи теории
графов представляются в виде специального рисунка – графа. Однако, это, как правило,
возможно только для простейших вариантов задач. Рисовать графы для задач с сотнями
вершин и тысячами дуг, если и возможно, то бессмысленно. Теряется главное
преимущество рисунка – наглядность. Кроме того, сегодня при решении задач теории
графов широко используется вычислительная техника, а для нее - решение задачи, заданной
рисунком – одно из самых неудобных представлений, какие можно придумать. А
наглядность компьютер понимает по-своему :-|
Граф G задается как совокупность двух сущностей: множества вершин Х и множества
соединений – множества дуг или ребер.Г . G = <Г, Х>,
Графически это может выглядеть следующим образом:
Традиционная «аналитическая» запись для этого рисунка будет:
Г
x1
= {x
2
} Г
x4
= {x
3
, x
3
}
Г
x2
= {x
2,
x
3
, x
4
} Г
x5
= {x
2
}
Г
x3
=
Другой способ задания графа - с помощью матрицы инциденций.
х
1
-1
х
2
+1 2 -1 -1 +1
х
3
+1 -1
х
4
+1 -1 +1
х
5
+1 -1
Самый популярный вид матрицы для графов – матрица смежностей
х1 х2 х3 х4 х5
х1 1
х2 1 1 1
х3 1
х4 1
х5 1
— 47 —
x
1
x
2
x
3
     Следует отметить некоторые практические особенности теории графов. Слово граф
     однокоренное со словом графика. Поэтому не удивительно, что многие задачи теории
     графов представляются в виде специального рисунка – графа. Однако, это, как правило,
     возможно только для простейших вариантов задач. Рисовать графы для задач с сотнями
     вершин и тысячами дуг, если и возможно, то бессмысленно. Теряется главное
     преимущество рисунка – наглядность. Кроме того, сегодня при решении задач теории
     графов широко используется вычислительная техника, а для нее - решение задачи, заданной
     рисунком – одно из самых неудобных представлений, какие можно придумать. А
     наглядность компьютер понимает по-своему :-|

     Граф G задается как совокупность двух сущностей: множества вершин Х и множества
     соединений – множества дуг или ребер.Г . G = <Г, Х>,
     Графически это может выглядеть следующим образом:

          x1
                        
                                 x2
                                          

x5                      
                                      
          
                                      x3
                   x4       

     Традиционная «аналитическая» запись для этого рисунка будет:

     Гx1 = {x2}                                Гx4 = {x3, x3}

     Гx2 = {x2, x3, x4}                        Гx5 = {x2}

     Гx3 = 

     Другой способ задания графа - с помощью матрицы инциденций.

                                                               
     х1        -1
     х2        +1           2         -1                        -1   +1
     х3                               +1       -1
     х4                                        +1      -1       +1
     х5                                                +1            -1


     Самый популярный вид матрицы для графов – матрица смежностей

               х1           х2        х3       х4      х5
     х1                     1
     х2                     1         1        1
     х3                                        1
     х4                                                1
     х5                     1


                                                                — 47 —

Страницы