Plaknes diagramma:
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.
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 1 ,r 2 ,r 3 ,r 4 ,r 5 .
Grafā ir četri galīgi apgabali, t.i., r 2 ,r 3 ,r 4 ,r 5 .
Ir tikai viens ierobežots apgabals, t.i., r 1
Plakano grafiku īpašības:
- Ja savienotam plakanam grafam G ir e malas un r apgabali, tad r ≦
Tas ir. - Ja savienotam plakanam grafam G ir e malas, v virsotnes un r apgabali, tad v-e+r=2.
- Ja savienotam plakanam grafam G ir e malas un v virsotnes, tad 3v-e≧6.
- Pilns grafiks K n ir plakana tad un tikai tad, ja n <5. < li>
- Pilnīgs divpusējs grafiks K mn ir plakana tad un tikai tad, ja m3.
Piemērs: Pierādiet, ka pilns grafs K 4 ir plakana.
Risinājums: Pilns grafiks K 4 satur 4 virsotnes un 6 malas.
Mēs zinām, ka savienotam plakanam grafikam 3v-e≧6. Līdz ar to K 4 , mums ir 3x4-6=6, kas apmierina īpašumu (3).
Tādējādi K 4 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 5 vai K 3.3
1. piemērs: Parādiet, ka K 5 ir neplakans.
Risinājums: Pilns grafiks K 5 satur 5 virsotnes un 10 malas.
Tagad savienotam plakanam grafikam 3v-e≧6.
Līdz ar to K 5 , 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 5 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 5 vai K 3.3 .
Risinājums: Ja noņemam malas (V 1 ,IN 4 ),(IN 3 ,IN 4 ) un (V 5 ,IN 4 ) grafiks G 1 , kļūst par homeomorfu K 5 .Līdz ar to tas nav plakans.
Ja noņemam malu V 2,V 7) grafiks G 2 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.
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 n ir n.
Risinājums: Krāsojums K n var 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∈V deg(v)=2e
Pierādījums: Lai G = (V, E) ir grafiks, kur V = {v 1 ,in 2 , . . . . . . . . . .} ir virsotņu kopa un E = {e 1 ,Tas ir 2 . . . . . . . . . .} 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∈V deg(v)=2e
