| Језик : |
|
| Енциклопедија заједница |Енциклопедија Одговори |Пошаљи питање |Речник Знање |Додај знања |
Повезан граф |
 |
|
Ацикличне повезан граф Скицирати У теорији графова, повезан граф заснован на концепту повезивања. У неусмереном графу Г, од темена до темена ВИ ВЈ постоји пут повезан (наравно од ВЈ да ви морате имати путању), онда кажемо ви и ВЈ је повезан. Ако је Г усмерен граф, онда ви и ВЈ повезати путању све ивице морају бити у истом смеру. Ако се било које две тачке на слици су повезани, онда је граф назива повезан граф. Повезивање мапа је основна природа сл.Строга дефиниција На графу Г = (В, Е) су тачке Кс и И, и ако постоји наизменични низ темена и ивица Γ = (к = В0-е1-В1-Е2-...-ЕК-(вк 1) = и) (где је потребно до ивице графа-ви (ви 1) припадају Е), два тачке Кс и И су повезани. Γ је комуникациони пут к, и, к, и су и почетну и крајњу тачку. Када је к = и, Γ се зове петља. Ако путања Γ ивице Појава удвојених различита, онда Γ је једноставан пут, иначе је компликован пут. Ако граф Г сваке две тачке повезане, онда је Г повезан граф. Слични концепти Повезаних компоненти: неусмерена граф Г је максимални повезани подграф од Г се назива спојене компоненте (или повезане компоненте). Повезан граф је само једна повезана компонента, то јест, своје, нису повезани неусмерена граф има више повезаних компоненти. Снажно повезан граф: усмерен граф Г = (В, Е), ако за било које две различите В теменима кии, и тамо од Кс на И и пут од к до и, онда Г је повезан Слика. Сходно томе, концепт снажно повезане компоненте. Снажно је повезан граф само снажно повезана компонента, то јест, за себе, нису чврсто повезани биграм снажно повезане компоненте имају вишеструке. Слабо повезан граф: биграм све режији Ивице замењују неусмерена ивицама, резултат граф се зове оригинална база мапа. Ако усмерен граф база карта је повезан граф, онда усмерен граф је слабо повезан граф. Примарни пут: пут различити једни од других у свим темена. Примарни пут ће бити из простог пут, али не важи обрнуто. Природа Неусмерена граф Г = (В, Е) је повезан, онда је број ивица је веће него једнак броју темена минус један: | Е |> = | В | -1, док обрнуто није истина. Ако је Г = (В, Е) бити усмерени граф, онда је снажно повезан граф је неопходан услов за број ивица је веће него једнак броју темена: | Е |> = | в |, док обрнуто није истина. Неусмерена граф без петљи је повезан ако и само ако је дрво које је еквивалентно: | Е | = | В | -1. Референтни Извор Фред Бакли, Марти Левинтер "Грапх Тхеори Сажети водич." Звездана Па Вангфенг Ћин Пекинг:. Тсингхуа Университи Пресс .2005 ВТТутте, Грапх Тхеори Цамбридге Университи Пресс.. 2004 |
| Корисник Преглед |
|
Но цомментс иет |
