Atšķirība starp virzienu un bez virziena grafiku

Režīms pret bez virziena grafiku

Diagramma ir matemātiska struktūra, kas sastāv no virsotņu un malu kopas. Diagramma attēlo objektu kopumu (ko attēlo virsotnes), kas savienoti caur dažām saitēm (apzīmētas ar malām). Izmantojot matemātiskos apzīmējumus, grafiku var attēlot ar G, kur G = (V, E) un V ir virsotņu kopa un E ir malu kopa. Neizvirzītā diagrammā nav virziena, kas saistīts ar malām, kuras savieno virsotnes. Virzītā grafikā ir virziens, kas saistīts ar malām, kuras savieno virsotnes.

Bez virziena grafiks

Kā jau minēts iepriekš, nevirzīts grafiks ir grafiks, kurā malās nav virziena, kas sasaista diagrammas virsotnes. 1. attēlā ir attēlots nevirzīts grafiks ar virsotņu kopu V = V1, V2, V3. Augšējā diagrammā esošo malu kopu var uzrakstīt kā V = (V1, V2), (V2, V3), (V1, V3). Var arī atzīmēt, ka nekas neliedz uzrakstīt malu kopu kā V = (V2, V1), (V3, V2), (V3, V1), jo malām nav virziena. Tāpēc malas nevirzītā grafikā nav sakārtotas pāros. Tā ir galvenā nevirzīta grafika īpašība. Neizvirzītus grafikus var izmantot, lai attēlotu simetriskas attiecības starp objektiem, kurus attēlo virsotnes. Piemēram, divvirzienu ceļu tīklu, kas savieno pilsētu kopu, var attēlot, izmantojot nevirzītu diagrammu. Pilsētas var attēlot ar virsotnēm grafikā, un malas attēlo divvirzienu ceļus, kas savieno pilsētas.

Režīms grafiks

Novirzīts grafiks ir grafiks, kurā grafika malām, kas savieno virsotnes, ir virziens. 2. attēlā ir parādīts novirzīts grafiks ar virsotņu kopu V = V1, V2, V3. Augšējā diagrammā esošo malu kopu var uzrakstīt kā V = (V1, V2), (V2, V3), (V1, V3). Neieviestā diagrammas malas ir sakārtotas pa pāriem. Formāli e malu novirzītā grafikā var attēlot ar sakārtotu pāri e = (x, y), kur x ir virsotne, ko sauc par e malas sākumu, avotu vai sākuma punktu, un virsotni y sauc par galu. , beigu virsotne vai gala punkts. Piemēram, ceļu tīklu, kas savieno pilsētu kopu, izmantojot vienvirziena ceļus, var attēlot, izmantojot nevirzītu diagrammu. Pilsētas var attēlot ar virsotnēm grafikā, un virzītās malas attēlo ceļus, kas savieno pilsētas, ņemot vērā virzienu, kādā satiksme plūst uz ceļa.

Kāda ir atšķirība starp Directed Graph un Undirected Graph?

Novirzītā grafikā mala ir sakārtots pāris, kur sakārtots pāris apzīmē malas virzienu, kas savieno abas virsotnes. No otras puses, nevirzītā grafikā mala ir nesakārtots pāris, jo ar malu nav saistīta virziena. Neizvērstus grafikus var izmantot, lai attēlotu simetriskas attiecības starp objektiem. Katra mezgla grāda un ārējā pakāpe nevirzītā diagrammā ir vienāda, bet tas neattiecas uz virzītu grafu. Ja matricu izmanto, lai attēlotu nevirzītu grafiku, matrica vienmēr kļūst par simetrisku grafiku, bet tas neattiecas uz virzītiem diagrammām. Neizvirzītu grafiku var pārveidot par virzītu grafu, aizstājot katru malu ar divām virzītām malām, kas iet pretējā virzienā. Tomēr nav iespējams pārveidot novirzītu grafiku par nevirzītu grafiku.