Grafu sauc par plakanu, ja to var uzzīmēt plaknē tā, ka mala nešķērsojas.

Piemērs: Attēlā parādītais grafiks ir plakans grafiks.

aktieris ranbir kapoor vecums

Diagrammas reģions: Aplūkosim plakanu grafiku G=(V,E). Apgabals ir definēts kā plaknes apgabals, kuru ierobežo malas un kuru nevar sīkāk sadalīt. Plakans grafiks sadala plānus vienā vai vairākos reģionos. Viens no šiem reģioniem būs bezgalīgs.

Ierobežots reģions: Ja apgabala laukums ir ierobežots, tad šo apgabalu sauc par ierobežotu apgabalu.

Bezgalīgs reģions: Ja apgabala laukums ir bezgalīgs, šo apgabalu sauc par bezgalīgu apgabalu. Plakanam grafikam ir tikai viens bezgalīgs apgabals.

Piemērs: Aplūkosim attēlā parādīto grafiku. Nosakiet reģionu, galīgo reģionu un bezgalīgā apgabala skaitu.

Risinājums: Iepriekš minētajā grafikā ir pieci reģioni, t.i., r₁,r₂,r₃,r₄,r₅.

Grafā ir četri galīgi apgabali, t.i., r₂,r₃,r₄,r₅.

Ir tikai viens ierobežots apgabals, t.i., r₁

Plakano grafiku īpašības:

1. Ja savienotam plakanam grafam G ir e malas un r apgabali, tad r ≦ Tas ir.
2. Ja savienotam plakanam grafam G ir e malas, v virsotnes un r apgabali, tad v-e+r=2.
3. Ja savienotam plakanam grafam G ir e malas un v virsotnes, tad 3v-e≧6.
4. Pilns grafiks K_nir plakana tad un tikai tad, ja n<5.< li>
5. Pilnīgs divpusējs grafiks K_mnir plakana tad un tikai tad, ja m3.

Piemērs: Pierādiet, ka pilns grafs K₄ir plakana.

Risinājums: Pilns grafiks K₄satur 4 virsotnes un 6 malas.

Mēs zinām, ka savienotam plakanam grafikam 3v-e≧6. Līdz ar to K₄, mums ir 3x4-6=6, kas apmierina īpašumu (3).

java druka

Tādējādi K₄ir plakans grafiks. Līdz ar to pierādīts.

Neplaknes diagramma:

Grafu sauc par neplanāru, ja to nevar uzzīmēt plaknē tā, lai mala nešķērsotos.

Piemērs: Attēlā parādītie grafiki ir neplanāri grafiki.

Šos grafikus nevar uzzīmēt plaknē tā, lai neviena mala nešķērsotos, tāpēc tie ir neplanāri grafi.

Neplanāru grafiku īpašības:

Grafs nav plakans tad un tikai tad, ja tajā ir K homeomorfs apakšgrāfs₅vai K_3.3

alfabēts līdz ciparam

1. piemērs: Parādiet, ka K₅ir neplakans.

Risinājums: Pilns grafiks K₅satur 5 virsotnes un 10 malas.

Tagad savienotam plakanam grafikam 3v-e≧6.

Līdz ar to K₅, mums ir 3 x 5-10=5 (kas neapmierina īpašību 3, jo tam ir jābūt lielākam vai vienādam ar 6).

Tādējādi K₅ir neplaknes grafs.

2. piemērs: Parādiet, ka attēlā parādītie grafiki nav plakani, atrodot apakšgrafu, kas ir homeomorfs ar K₅vai K_3.3.

Risinājums: Ja noņemam malas (V₁,IN₄),(IN₃,IN₄) un (V₅,IN₄) grafiks G₁, kļūst par homeomorfu K₅.Līdz ar to tas nav plakans.

Ja noņemam malu V_2,V7) grafiks G₂kļūst homeomorfs K_3.3.Līdz ar to tas ir neplanārs.

Grafika krāsošana:

Pieņemsim, ka G= (V,E) ir grafs bez vairākām malām. G virsotņu krāsojums ir krāsu piešķiršana G virsotnēm tā, ka blakus esošajām virsotnēm ir dažādas krāsas. Grafiks G ir M-krāsains, ja pastāv G krāsojums, kurā tiek izmantotas M krāsas.

Pareiza krāsošana: Krāsošana ir pareiza, ja jebkurām divām blakus esošajām virsotnēm u un v ir dažādas krāsas, pretējā gadījumā to sauc par nepareizu krāsojumu.

rdbms

Piemērs: Apsveriet šādu grafiku un krāsu C={r, w, b, y}. Pareizi nokrāsojiet grafiku, izmantojot visas krāsas vai mazāk krāsu.

Attēlā parādītais grafiks ir vismaz 3 krāsojams, tātad x(G)=3

Risinājums: Attēlā parādīts grafiks, kas pareizi iekrāsots ar visām četrām krāsām.

Attēlā parādīts grafiks, kas pareizi iekrāsots ar trim krāsām.

G hromatiskais skaitlis: Minimālo krāsu skaitu, kas nepieciešams, lai iegūtu pareizu grafika G krāsojumu, sauc par G hromatisko skaitu un apzīmē ar x(G).

Piemērs: K hromatiskais skaitlis_nir n.

Risinājums: Krāsojums K_nvar konstruēt, izmantojot n krāsas, katrai virsotnei piešķirot dažādas krāsas. Divām virsotnēm nevar piešķirt vienādas krāsas, jo katras divas šī grafika virsotnes atrodas blakus. Līdz ar to K hromatiskais skaitlis_n=n.

Grafiku krāsošanas pielietojumi

Daži grafiku krāsošanas pielietojumi ietver:

• Reģistra piešķiršana
• Kartes krāsošana
• Divpusējā grafika pārbaude
• Mobilo radiofrekvenču piešķiršana
• Laika grafika sastādīšana utt.

Nosakiet un pierādiet Rokasspiediena teorēmu.

Rokasspiediena teorēma: Visu grafa G virsotņu pakāpju summa ir vienāda ar divreiz lielāku malu skaitu grafā.

Matemātiski to var izteikt šādi:

∑_v∈Vdeg(v)=2e

Pierādījums: Lai G = (V, E) ir grafiks, kur V = {v₁,in₂, . . . . . . . . . .} ir virsotņu kopa un E = {e₁,Tas ir₂. . . . . . . . . .} ir malu kopa. Mēs zinām, ka katra mala atrodas starp divām virsotnēm, tāpēc katrai virsotnei tā nodrošina pirmo pakāpi. Tādējādi katra mala grafam piešķir otro pakāpi. Tātad visu virsotņu pakāpju summa ir vienāda ar divkāršu malu skaitu G.

Tādējādi ∑_v∈Vdeg(v)=2e

python baiti uz virkni