Графи2
| Информационни технологии | 2009-12-04 | 73 сваляния |
Графи
-
Основни понятия.
Графът (фиг.1) е съвкупност от възли (върхове) и дъги (ребра), които ги свързват. Графът се нарича ориентиран, в случай, че са дефинирани посоки на дъгите.Тогава се говори за стрелки, вместо за дъги. Броят на влизащите в даден възел стрелки се нарича входна степен за този възел, а броят на излизащите от даден възел стрелки негова изходна степен. Дървото е граф, при който точно един връх има входна степен 0, а всички останали са с входна степен 1.
Етикетиран граф (мрежа) е граф, чиито възли или дъги са именувани с цел еднозначна идентификация. Например, етикети на възли могат да бъдат имена на градове, а етикети на стрелки - разстоянията между тях.
Път в граф е последователност от стрелки, свързващи два възела.. Един връх се нарича достижим от друг връх, ако съществува път между тях. Дължина на пътя е броят на съдържащите се в него стрелки. Цикъл е ненулев път, започващ и завършващ с един и същи възел. Примка е цикъл с дължина 1. Дървото е граф без цикли, при който между два възела съществува най-много един път. Коренен граф е граф, който има възел, наречен корен, такъв, че съществува път от корена до всеки възел на графа. Дървото винаги има корен.
Понятията, които се използват за описание на връзките между възлите са родител, наследник, син, брат. Ако от възел a има стрелки към възли b и c, то a се нарича родител на b и c, а b и c наследници (синове) на a. Наследниците от даден възел са братя помежду си. Листо е възел без наследници.
Настроен граф се нарича граф със зададени множество на началните (инициални) и множество на финалните (крайни) възли. При настроени графи обикновено се интересуваме от пътищата, започващи с начален и завършващи с финален възел.
-
Представяне на графи на ПАСКАЛ.
Нека да разгледаме следния граф:
фиг.1
2.1.Чрез статични структури.
Най-често използвания начин е представянето на таблицата на съседство на графа чрез двумерен масив.
| V | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2.2. Чрез динамични структури.
 |
 |
 |
 |
 |
 |
 |
 |
Тагове от реферата: свърз, ориентира, Дефинирани, посоки, върхове, понятия, съвкупност, основни
