Atšķirība Starp Virzīto Un Nenovirzīto Grafiku

2024 Autors: Mildred Bawerman | [email protected]. Pēdējoreiz modificēts: 2023-12-16 08:40

Virzīts vs nenovirzīts grafiks

Grafiks ir matemātiska struktūra, kas sastāv no virsotņu un malu kopas. Grafiks attēlo objektu kopu (attēloti ar virsotnēm), kas ir savienoti, izmantojot dažas saites (ko attēlo malas). Izmantojot matemātiskus apzīmējumus, grafiku var attēlot ar G, kur G = (V, E) un V ir virsotņu kopa, un E ir malu kopa. Nevirzītā grafikā nav virziena, kas saistīts ar malām, kas savieno virsotnes. Virzītā grafikā ir virziens, kas saistīts ar malām, kas savieno virsotnes.

Nevirzīts grafiks

Kā minēts iepriekš, nenovirzīts grafiks ir grafiks, kurā malās nav virziena, kas saista diagrammas virsotnes. 1. attēlā attēlots nenovirzīts grafiks ar virsotņu kopu V = {V1, V2, V3}. Malu kopu augstāk redzamajā grafikā var ierakstīt šādi: 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 nenovirzītā grafika malas nav sakārtoti pāri. Šī ir galvenā nenovirzītā grafika īpašība. Nenovirzī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 nenovirzītu grafiku. Pilsētas grafikā var attēlot ar virsotnēm, un malas attēlo divvirzienu ceļus, kas savieno pilsētas.

Virzīts grafiks

Virzīts grafiks ir grafiks, kurā diagrammas malām, kas savieno virsotnes, ir virziens. 2. attēlā attēlots virzīts grafiks ar virsotņu kopu V = {V1, V2, V3}. Malu kopu augstāk redzamajā diagrammā var ierakstīt šādi: V = {(V1, V2), (V2, V3), (V1, V3)}. Nevirzītā grafika malas ir sakārtotas pāros. Formāli malu e virzītā grafikā var attēlot ar sakārtotu pāri e = (x, y), kur x ir virsotne, ko sauc par malas e izcelsmi, avotu vai sākuma punktu, un virsotni y sauc par galu, beidzot virsotni vai galapunktu. Piemēram, ceļu tīklu, kas savieno pilsētu kopu, izmantojot vienvirziena ceļus, var attēlot, izmantojot nenovirzītu grafiku. Pilsētas grafikā var attēlot ar virsotnēm, un virzītās malas attēlo ceļus, kas savieno pilsētas, ņemot vērā ceļu plūsmas virzienu.

Kāda ir atšķirība starp virzīto grafiku un nevirzīto grafiku?

Virzītā grafikā mala ir sakārtots pāris, kur sakārtotais pāris apzīmē malas virzienu, kas saista abas virsotnes. No otras puses, nenovirzītā grafikā 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 pakāpe un pakāpe nenovirzītā grafikā ir vienāda, taču tas nav taisnība virzītam grafikam. Izmantojot matricu, lai attēlotu nenovirzītu grafu, matrica vienmēr kļūst par simetrisku grafiku, bet tas nav taisnība virzītiem grafikiem. Nenovirzītu grafu var pārveidot par virzītu grafiku, nomainot katru malu ar divām virzītām malām, kas iet pretējā virzienā. Tomēr nav iespējams pārveidot virzītu diagrammu par nenovirzītu.