Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 7
Текст из файла (страница 7)
Упорядоченный (помеченный) граф матрицы А, обозначаемый 6л = (Хл, Ел), — это граф, для которого й1 вершин 6л пронумерованы числами от 1 до )У и (хь хД ~ Ел тогда и только й 8.1. Терминология и некоторые олределения 45 О1Ф « ~ф:й э «ОЗ « 04 О* «э® Матрица 4 Рис. 3.1.1. Матрица и ее помеченный граф. Символ е обозначает ненулевой элемент А. О1 Э «с ф «с' «с «СЗ) « *Оц ~ «с® Ф «с Д6 й а ж 02 «с Ф «4 ОЗ « «с ® Ф Ф (5) Ое Рнс. 3.1.2. Граф рисунка 3!.! при различных помечивапиях и структуры соответствующих матриц. Здесь Р и 4е обозначают матрицы перестановок. 46 Гя. я, Нвяоторьтв сведения иэ теории графов тогда, когда ап = а„чьО, т'чь1. Здесь х, — узел Х" с меткой й Рис.
3.1Л иллюстрирует структуру матрицы и ее помеченного графа. Чтобы подчеркнуть соответствие Его диагонального элемента матрицы с узлом 1 ее графа, мы указываем этот элемент как 1 в кружочке. Внедиагональиые ненулевые элементы обозначены символом Если Р ~ 1 — произвольная (М Х ту)-матрица перестановки, то непомеченные графы матриц А и РАР' совпадают, а соответствующие помсчивання различны.
Таким образом, непомеченный граф А представляет структуру А без упоминания о каком-либо конкретном упорядочении. Он изображает класс эквивалентности матриц РАР', где Р— любая (М рс', Ат) -матрица перестановки. Отыскание «хорошей» перестановки для А можно рассматривать как отыскание хорошего помечивания для ее графа. Рис. 3.!.2 иллюстрирует сказанное. Некоторые определения теории графов связаны с непомеченными графами. Чтобы интерпретировать такие определения в матричных терминах, нужно ввести соответствующую матрицу, что немедленно приводит к упорядочению графа.
Хотя это и не должно вызвать недо(газумсний, читателю все же не следует приписывать какого-либо значения конкретному упорядочению, выбираемому в наших матричных примерах и интерпретациях. Когда мы говорим о «матрице, соответствующей графу 6», мы либо оговариваем некоторое упорядочение а для 6, либо подразумеваем, что упорядочение может быть произвольным, Два узла х и у из 6 называются смежными, если (х, у) бвЕ. Если У ~ Х '), го смежное множество для У есть Аб)(У)=(х~ Х вЂ” У ~(х, у) ~Е для некоторого уев У). (3.1.1) Словами: А4(У) есть множество узлов 6, не принадлежащих У, но смежных хотя бы с одним узлом из У. Рис.
3.1,3 иллюстрирует матричную интерпретацию множества Ат(1(У), Для удобства узлы множества У были помечены последовательными целыми числами. Если У имеет единственную вершину у, будем писать Аг)1(у) вместо формально правильного Аб)((у)). Для У~ Х степень У, обозначаемая через Ред(У), есть число (Аб)(У) ), где (5) — обозначение числа элементов множества 5.
Опять-таки, если У имеет единственную вершину у, будем писать Реп(у), а не Оеп((у)). Например, на рис. 3.1,3 Оеп(ха) = 3. Частью 6' = (Х', Е') графа 6 называется граф, для которого Хтс Х и Е'с Е. Если У~Х, то подграф 6(У) — это часть (У, Е(У)) графа 6, такая, что Е(У) ° ((х, у) ек Е 1х ~ У, у яв У). (3.1.2) ') Здесь и всюду в книге обоэиачеиие У т= Х допускает, что У может совпадать с Х. Если важно, чтобы У было собственным подмножеством Х, ьто будет явно оговариваться, На матричном языке подграф О(У) — это граф матрицы, полу- ченной из матрицы графа 6 вычеркиванием всех строк и столб- цов, кроме тех, которые соответствуют У. Это иллюстрируется рисунком 3.1,4.
Ф 103 Ф Ой 05* У =(лиха),,4д(~) =( Ряс. ЗЛ.З. Иллюстрация к понятию смежного множества для множества у сх. Подграф называется кликой, если все его узлы попарно смежны. В матричной терминологии клике соответствует заполненная подматрица. Например, 6((ха х4)) является кликой. 1' =(% розов) Матрааа ааРграйра гр0') Рис. 3.1.4. Пример подграфа 6(У) и соответствующей подматрицы. Исходный граф 0 изображен на рис.
3.1.1. Пример на рис. 3.1.4 иллюстрирует понятие, которое мы сейчас исследуем, а именно связность графа. Если х и у — различные узлы О, то пптем из х в у длины 1 =» 1 называется упорядоченное множество из !+1 различных узлов (оп ою ., оиы), О2 Ф 03 Ое Д ЗЛ. Терминология и некоторые определения 47 ф ! зй ! — 4 02 — Дз ® 48 Гя. 3. Неяоторвсе сведения иэ теории графов такое, что о,.„~Аб1(о,), 1=1,2.....
1, причем о, =х, оры = =у. Граф называется связным, если каждая пара различных узлов соединена хотя бы одним путем. В противном случае 6 несвязен и состоит из двух или более связнасх компонент. Если говорить о матричных аналогиях, то должно быть ясно, что для алга: (эсьхглсэ, вРтт1 ~Об~ ~О рис. а1. 6.Путь в графе и соответствующая матричная интерпретация.
несвязного графа 6, состоящего из й связных компонент, при последовательном помечивании этих компонент соответствующая матрица будет блоено-диагональной и каждый диагональный блок ассоциирован со связной компонентой. Граф 6(У) на рис. 3.1.4 упорядочен именно так, и соответствующая ему матрица — блочно-диагональная.
Рис. ЗЛ.Ь показывает некоторый путь в графе и его матричную интерпретацию. Наконец, множество Ус:Х называется разделителем связного графа 6, если подграф 6(Х вЂ” У) несвязен. Так, например, У= (ха, хо хв) — разделитель графа на рис. ЗЛ.5, потому что .граф 6(Х вЂ” У) состоит из трех компонент с узловыми множест- вами (хД, (хэ) и (ха, хт) соответственно. 4 8.2. Машинное представление графов 49 Упражнения 3.1.1. Симметричная матрица А называется разлоагилой, есл» найдется матрица перестановки и, такая, что (А„о ) В противном случае.4 называется неразложи,иой.
Показать, что симметричная матрица А неразложима тогда н только тогда, когда ассоциированный с ней граф 6' связен. 3.!.2. Пусть А — симметричная матрица. Показзтгь что матрица А обладает свойстеол распространения (см. упр. 2,2.3) тогда н только тогда, когда в ассоциированном с ней графе 0л существует путь (яь лз, ..., лн). 3.1.3.
Охарактеризовать графы, ассоциированные со следукзщнмн матрн. цамн: 4) ненни ннн » Ф н » н Ф Ф Ф Ф нн Фннннння й 3.2. Машинное представление графов Характеристики машинных алгоритмов, оперируюших с гра. фами, обычно весьма чувствительны к способу их представления. В наших задачах. основной операцией с графами будет дплмоу номер узза 1 2 3 4 5 6 Рнс.
3.2.1. Пример структуры смежности. выявление отношений смежности между узлами. Поэтому мь! нуждаемся в способе представления, позволяющем легко установить свойства смежности в графе и притом экономичном в смысле памяти, $0 Гл. 8 ()еиоторвве сведения из теории грифов Пусть б =(Х, Е) — граф с А1 узлами. Списком смежности для хее Х называется список, содержащий все узлы из А((1(х). Структура смежности графа 6 — это просто множество списков смежности для всех хы Х. Такую структуру можно реализовать очень просто и экономично, храня списки смежности последовательно в одномерном массиве АРЗ(ч)С'1'; дополнительный индексный массив ХАШ длины Л)+ 1 содержит указатели начала каждого списка смежности в массиве АШХС'1'. Пример показан на б'ааеРи Рис.
3.2.2. Таблица связей графа на рис. 3.2.1. Неисполъзуемые позиции таб- лицы указаны прочеркамн. рис. 3.2.1. Из программистских соображений часто бывает удобно иметь в ХАРД дополнительную компоненту, так чтобы переменная ХАШ(А)+!) указь(вала адрес первой свободной ячейки в массиве АР3(ч(С'1' (см. рис. 3.2.1). Ясно, что общая длина массивов при такой схеме хранения равна (Х(+2(Е(+ 1. Для доступа к соседям данного узла можно воспользоваться следующим программным сегментом: МВИВЕ6 - ХЛО)<МОВЕ) МВНЕМО ХЛОЯ(МООЕ в 1) - 1 1н (МВВЕМО .1.т.
МВВВЕ6) 60 ТО 200 ОО 100 1 МВИВЕ6, МВИЕМО млвои - лптмст<ц 100 сомт1мое 2ОО Хотя во всех наших программах, оперирующих с графами, используется описанная выше схема хранения часто применяют и другие. Распространенной схемой хранения является простая таблица связей, имеющая А) строк и и) столбцов, где и = шах(Реп(х) (хеи Х). Список смежности 1-го узла хранится в 1-й строке. Эта схема хранения может быть очень неэффективной, если многие узлы имеют степень меньшую, чем т. В качестве примера на рис. 3,2.2 приведена таблица связей для графа рисунка 3.2,1.
1 2 3 4 5 б 2 б 1 3 4 2 5 2 3 б 1 5 3 3.Е Машинное представление графов 31 Описанные до сих пор две схемы имеют очевидный недостаток. Если степени узлов неизвестны а рпотй то трудно построить схему хранения графа, заданного списком ребер, поскольку неизвестны форматы отдельных списков смежности. Эту трудность можно преодолеть, вводя поле связей.
На рис. 3.2.3 изображен т ! 1Ч8кЗ Е1ЫК ееЕАО 1 мзгг 2 Э 1 3 4 12 4 ! ) ! / / l 5 8 -~ 5 6 5 ~з 8 Рис. 3,2.3 Связные списки смежности хая графе рис. 3.2.1. пример такой схемы для графа рисунка 3.2.1. Значением указателя НЕАР(1) является начало списка смежности 1-го узла; при этом в массиве г)ВКЗ находим соседа узла й а в массиве 11ИК вЂ” указатель расположения следующего соседа этого узла. Пусть, например, нужно отыскать соседей узла 5. Значение НЕАО(5) раино 8. Обращаемся к МВЙБ(8) и получаем 3. Это— один из соседей узла 5. Переходим к 1(ИК(8) и находим там 2. Это значит, что следующего соседа узла 5 нужно искать в ХВ)с8(2), где хранится 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
