Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 5 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

5
Задача 31
. По портрету СПОМ А построить помеченный неориентированный
граф G.
Задача 32. По заданному графу G восстановить портрет матрицы A.
Замечание.
Символ * означает, что вершина i нами уже пройдена (т. е. все
инцидентные ей ребра мы прошли).
Задача 33.
Для графа G из задачи 32:
1) перечислить все смежные вершины и указать их степень
(например, вершины 3 и 5: deg 3=1, deg 5=4);
2) найти смежное множество для вершин 1, 6
(W={1, 6}, Adj(W)={2, 4, 5});
3) указать несколько путей, соединяющих вершины 1,4 и их длину
(например, путь (1,6,4) длины 2 или путь (1,2,5,4) длины 3);
4) найти расстояние между вершинами 1,4 и 1,2
(d(1,4)=2, d(1,2)=1);
5) найти эксцентриситет вершины 2 (е(2)=2);
6) найти диаметр графа (diam G = 3, т. к. е(6)=е(3)=3);
7) указать периферийные вершины ({3,6});
8) указать ППВ (например, {3,6});
9) указать циклы (например, (1,6,4,5,1), (2,5,4,6,1,2));
10) найти клику (например, (2,1,5,2));
11) указать один частичный граф и один подграф
(например, G
*
(V
*
,E
*
), где V
*
={1,5,4}, Е
*
={(1,5)}- подграф,
G
**
(V
**
,E
**
), где V
**
={1,5,4}, E
**
={(1,5), (5,4)}- частичный граф);
12) указать разделитель (например, вершина 5 разбивает граф G на две
связные компоненты с вершинами {2,1,6,4} и {3}).
4
1
=
xxx
xxx
xx
xx
xx
xx
А
6
2
5
3
2
1
4
5
3
6
=
xxx
xxxxx
xxx
xx
xxx
xxxx
А
*
*
*
**
                                    5

Задача 31. По портрету СПОМ А построить помеченный неориентированный
           граф G.

                      x        x
                                 
                       x   x                         1                2
                         x   x                            6
                    А=           
                       x   x     
                                                       5
                         x   x x
                      x                                       3       4
                             x x 

Задача 32. По заданному графу G восстановить портрет матрицы A.

Замечание. Символ * означает, что вершина i нами уже пройдена (т. е. все
 инцидентные ей ребра мы прошли).

                *               *               *      x x     x x
                    2                       3                      
                                5                      x x     x   
                                                           x   x 
                                        *
                    *   1           4               А =            
                                                             x x x
                                                       x x x x x 
                            6                                      
                                                       x     x   x 
                                                                   

Задача 33. Для графа G из задачи 32:
      1) перечислить все смежные вершины и указать их степень
         (например, вершины 3 и 5: deg 3=1, deg 5=4);
      2) найти смежное множество для вершин 1, 6
         (W={1, 6}, Adj(W)={2, 4, 5});
      3) указать несколько путей, соединяющих вершины 1,4 и их длину
         (например, путь (1,6,4) длины 2 или путь (1,2,5,4) длины 3);
      4) найти расстояние между вершинами 1,4 и 1,2
          (d(1,4)=2, d(1,2)=1);
      5) найти эксцентриситет вершины 2 (е(2)=2);
      6) найти диаметр графа (diam G = 3, т. к. е(6)=е(3)=3);
      7) указать периферийные вершины ({3,6});
      8) указать ППВ (например, {3,6});
      9) указать циклы (например, (1,6,4,5,1), (2,5,4,6,1,2));
      10) найти клику (например, (2,1,5,2));
      11) указать один частичный граф и один подграф
          (например, G*(V*,E*), где V*={1,5,4}, Е*={(1,5)}- подграф,
          G**(V**,E**), где V**={1,5,4}, E**={(1,5), (5,4)}- частичный граф);
      12) указать разделитель (например, вершина 5 разбивает граф G на две
           связные компоненты с вершинами {2,1,6,4} и {3}).

Страницы