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

                                     21



             1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
             6   205 15 13 7 1 16 14 4 12 11 18 17 10        2 3 19 9 8
     1    6 *   * *                                                       
                                                                          
     2   20 *   * *        *                                              
     3    5 *   * *        *                                              
                                                                          
     4   15          * *           *                                      
     5   13 
                     * *           *                                      
                                                                           
     6    7     * *        * *            *                               
                                                                          
     7    1                * * *          *                               
     8   16                  * * *        *                               
                                                                          
     9   14          * *        * *       *                               
    10    4                          * *     * *                          
                                                                          
    11   12                          * *        *                         
    12   11                * * * *        * *      *                      
                                                                          
    13   18                          *    * * * *           *             
                                                                          
    14   17                          * *     * *            *             
    15   10                               * *      *        *     * *     
                                                                          
    16    2                                  * * *          *        *    
    17    3                                                     * *      *
                                                                          
    18   19                                             *       * * *    *
    19    9                                             * *       * *    *
                                                                          
    20    8                                                    * * *    *
                                                                           

                      § 11. Метод вложенных сечений

                            11.1. Основные идеи
    Это один из наиболее эффективных и широко используемых методов
уменьшения объёма заполнения симметричных матриц. Его идея вытекает из
теоремы Джорджа-Лю.
    Пусть есть некоторый разделитель S={vk}, где
               vk∈V={v1,v2, ,vk-1, vk, vk+1, , vn}.
  Считаем, что вершины vi (i=1,...,n) перенумерованы таким образом, что после
удаления вершины vk мы получим две связные компоненты R1={v1, ,vk-1} и
R2={vk+1, , vn}. Если вершину vk поместим в конец (т.е. k→ n) и перенумеруем