Directed vs Undirected Graph
Grafs ir matemātiska struktūra, kas sastāv no virsotņu un malu kopas. Grafiks attēlo objektu kopu (attēlotas ar virsotnēm), kas ir savienotas caur dažām saitēm (attēlotas 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 šķautņu kopa. Nevirzītā grafā nav virziena, kas saistīts ar malām, kas savieno virsotnes. Virzītā grafā ir virziens, kas saistīts ar malām, kas savieno virsotnes.
Nevirzīts grafiks
Kā minēts iepriekš, nevirzīts grafs ir grafs, kurā malās, kas savieno grafa virsotnes, nav virziena.1. attēlā ir attēlots nevirzīts grafs ar virsotņu kopu V={V1, V2, V3}. Malu kopu iepriekš minētajā grafikā var uzrakstīt kā V={(V1, V2), (V2, V3), (V1, V3)}. Var arī atzīmēt, ka nekas neliedz rakstīt malu kopu kā V={(V2, V1), (V3, V2), (V3, V1)}, jo malām nav virziena. Tāpēc malas nevirzītā grafā nav sakārtoti pāri. Šī ir galvenā nevirzīta grafika īpašība. Nevirzī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 grafiku. Pilsētas var attēlot ar virsotnēm diagrammā, un malas attēlo divvirzienu ceļus, kas savieno pilsētas.
Režisēts grafiks
Virzots grafs ir grafiks, kurā grafa malām, kas savieno virsotnes, ir virziens. 2. attēlā ir attēlots virzīts grafs ar virsotņu kopu V={V1, V2, V3}. Malu kopu iepriekš minētajā grafikā var uzrakstīt kā V={(V1, V2), (V2, V3), (V1, V3)}. Malas nevirzītā grafikā ir sakārtoti pāri. Formāli malu e virzītā grafā var attēlot ar sakārtotu pāri e=(x, y), kur x ir virsotne, ko sauc par malas e sākumpunktu, avotu vai sākuma punktu, bet virsotni y sauc par galu., beigu virsotne vai galapunkts. Piemēram, ceļu tīklu, kas savieno pilsētu kopu, izmantojot vienvirziena ceļus, var attēlot, izmantojot nevirzītu grafiku. 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ā satiksmes plūsmas virzienu uz ceļa.
Kāda ir atšķirība starp virzīto grafiku un nevirzīto grafiku?
Virzītā grafā mala ir sakārtots pāris, kur sakārtotais pāris apzīmē malas virzienu, kas savieno abas virsotnes. No otras puses, nevirzītā grafā mala ir nesakārtots pāris, jo ar malu nav saistīts virziens. Nevirzītus grafikus var izmantot, lai attēlotu simetriskas attiecības starp objektiem. Katra mezgla iekšējais un ārējās pakāpes līmenis nevirzītā grafikā ir vienāds, taču tas neattiecas uz virzītu grafiku. Izmantojot matricu, lai attēlotu nevirzītu grafiku, matrica vienmēr kļūst par simetrisku grafiku, bet tas neattiecas uz virzītiem grafikiem. Nevirzītu grafiku var pārvērst par virzītu grafiku, aizstājot katru malu ar divām vērstām malām, kas iet pretējā virzienā. Tomēr nav iespējams pārvērst virzītu grafiku par nevirzītu grafiku.
