Teoria grafurilor, dezvoltându-se paralel cu algebra modernã, ºi-a fãurit un limbaj al sãu ºi însãºi noþiunea de graf a cãpãtat mai multe accepþii. Teoria grafurilor este prezentatã în sensul lui Koning ºi Berge
Yüklə 175,66 Kb.
|
§1. Noþiunea de graf Fie X ºi Y douã mulþimi date, o lege µ § care face sã corespundã fiecãrui element µ § un element bine definit din Y notat cu µ §, se numeºte aplicaþie univocã a lui X ºi Y, sau o funcþie definitã în X cu valori în Y. O aplicaþie à definitã pe X cu valori în Y, care face sã corespundã fiecãrui element x a lui X o submulþime a lui Y notatã cu µ §, se numeºte aplicaþie multivocã à a lui X în Y. Putem avea µ §. Fie X o mulþime ºi µ §. Dacã µ § atunci imaginea lui A prin aplicaþia à este µ §. Dacã A1, A2, ...,An sunt submulþimile lui X avem: 10. µ §
20. µ § 30. Dacã Ä este o altã aplicaþie a lui X în X produsul de compoziþie ÃÄ este aplicaþie definitã prin: µ § Aplicaþiile Ã2, Ã3, ...sunt definite prin: µ § Ã2x=Ã(Ãx) Ã3x=Ã(Ã3x) ... etc. 40. Închiderea tranzitivã a lui à este o aplicaþie µ § a lui X în X definitã prin µ § 50. Inversa aplicaþiei à este aplicaþia Ã-1 definitã prin: µ § Dacã B este submulþime a lui X se poate atunci scrie: µ § Exemplul 1. X = mulþimea de indivizi, iar x un individ Ãx = mulþimea copiilor lui x µ § = mulþimea nepoþilor lui x µ § = mulþimea formatã din x, copiii lui x ºi nepoþii lui x. Exemplul 2
Avem apoi: µ § = mulþimea poziþiilor care pot fi obþinute în trei mutãri dupã poziþia lui x µ § = mulþimea poziþiilor care pot fi întâlnite imediat sau mai târziu dupã poziþia lui x µ § (cu µ §) este mulþimea poziþiilor care pot deveni într-o singurã mutare o poziþie a lui A Acest sistem de notaþie permite sã se punã sub formã de formulã mulþimea poziþiilor avute în vedere ºi de a reduce unele proprietãþi. În cazul jocului de ºah, regula este complet determinatã de mulþimea X ºi aplicaþia Ã, dar din cauza unui mare numãr de poziþii posibile va fi imposibil sã se reprezinte poziþiile prin puncte ºi aplicaþia à prin sãgeþi unind unele dintre aceste puncte. Se numeºte graf ºi se noteazã cu µ § perechea formatã din mulþimea X ºi o aplicaþie multivocã a lui X în X. Când este posibil, elementele mulþimii X vor fi reprezentate prin puncte ale planului ºi dacã douã puncte x ºi y sunt astfel încât µ § vom duce o linie continuã prevãzutã cu o sãgeatã de la x spre y, figura de mai jos:
Atunci graful G=(X,Ã) poate fi notat ºi sub forma G=(X,U). Un subgraf al grafului G =(X, Ã) este prin definiþie un graf G’= (A, ÃA), unde µ §, iar µ §. Un graf parþial al lui G = (X, Ã) este prin definiþie un graf de forma G”= (X, Ä) unde pentru orice x, Äx = Ãx. Un subgraf parþial al lui G = (X, Ã) este prin definiþie un graf de forma (A, ÄA) unde µ § ºi µ §. Pentru un arc u = (a, b), vârful a este extremitate iniþialã, iar b este extremitate finalã sau terminalã. Douã arce u ºi v se numesc adiacente dacã sunt distincte ºi au o extremitate comunã. Se spune cã vârfurile x ºi y sunt adiacente dacã sunt distincte ºi existã un arc u = (x,y). Se spune cã arcul u este incident cu vârful x spre exterior dacã x este extremitate iniþialã a lui u ºi dacã extremitatea terminalã a lui u este diferitã de x. Se defineºte la fel un arc incident spre interior. Se spune cã un arc u este incident cu A spre exterior, unde A este o mulþime de vârfuri date, dacã u = (a, x) cu µ § ºi µ §. Mulþimea arcelor incidente cu o mulþime A spre exterior se noteazã µ §, iar mulþimea arcelor incidente cu A se noteazã cu µ §. Mulþimea arcelor incidente cu A se noteazã µ §. În graful G = (X, U) se numeºte drum un ºir (u1, u2, ...) de arce, astfel încât extremitatea terminalã a fiecãrui arc coincide cu extremitatea iniþialã a arcului urmãtor. Un drum este simplu dacã nu foloseºte de douã ori acelaºi arc ºi compus în caz contrar. Dacã drumul ì întâlneºte succesiv vârfurile x1, x2, ..., xk, xk+1 îl notãm ì = [x1, x2, ..., xk, xk+1]. Un drumm care nu trece de douã ori prin acelaºi vârf se numeºte drum elementar. Un drum poate fi finit sau infinit. Un circuit este un drum finit ì = [x1, x2 ... xk] unde x1 = xk. Circuitul este elementar dacã pornim dintr-un drum elementar. Lungimea unui drum ì = (u1, u2, ..., uk) este numãrul arcelor ºirului ºi o notãm cu l(u), iar dacã drumul este infinit atunci l(u) = ‡. Se numeºte buclã un circuit de lungime 1, format dintr-un singur arc (x, x). Un graf G = (X, U) se numeºte simetric dacã din µ § (într-un graf simetric douã vârfuri adiacente sunt legate între ele prin douã arce orientate opus unul celuilalt). Pentru a simplifica lucrurile convenim sã unim cele douã vârfuri printr-o singurã linie continuã fãrã sãgeþi pe ea. Un graf G = (X, U) se zice antisimetric dacã din µ § (orice pereche de vârfuri adiacente sunt legate între ele într-o singurã direcþie). Un graf G = (X, U) se numeºte complet dacã µ § (orice perche de vârfuri este legatã cel puþin în una din cele douã direcþii). Un graf G = (X, U) se numeºte tare conex dacã oricare ar fi vârfurile x ºi y, cu µ §, existã un drum care pleacã din x la y. În vârful G = (X, U) o muchie este, prin definiþie, o mulþime de douã vârfuri x ºi y astfel ca µ § sau µ §. Aceastã noþiune nu trebuie confundatã cu cea de arc care presupune ºi o orientare. Convenim ca mulþimea muchiilor sã o notãm cu U, iar muchiile cu literele: u, v... Un lanþ este un ºir de muchii (u1, u2, ...) fiecare muchie uk fiind legatã de muchia uk-1 printr-o extremitate ºi de uk+1 prin cealaltã extremitate. Un lanþ este simplu dacã muchiile care-l formeazã sunt diferite între ele ºi este compus în celelalte cazuri. Un ciclu este un lanþ finit care pleacã din x ºi ajunge tot în x. Ciclul este simplu dacã muchiile care îl compun sunt diferite între ele ºi compus în celelalte cazuri. Ciclul este elementar dacã orice vârf din acest ciclu este întâlnit o singurã datã. Un graf este conex dacã pentru orice pereche de vârfuri distincte existã un lanþ plecând de la un vârf la celãlalt. Un graf tare conex este ºi conex însã reciproc nu este adevãrat . Notãm cu µ § mulþimea compusã din vârful a dat ºi din toate vârfurile grafului care pot fi unite cu vârful a printr-un lanþ. O componentã comunã este subgraful generat de o mulþime de forma Ca. Teoremã 1. Diferite componente ale grafului G = (X, Ã) formeazã o partiþie a lui X, adicã: (1) µ § (2) µ §
(3) µ § Demonstraþie: (1) este adevãrat, pentru cã µ § (2) presupunem cã µ § ºi arãtãm cã Ca = Cb. Fie µ §, acest vârf poate fi legat printr-un lanþ de a ºi b, deci poate fi legat cu b, deci µ §, deci µ §. Analog µ §. Relaþia (3) are loc deoarece µ § Teoremã 2. Un graf este conex dacã ºi numai dacã are o singurã componentã conexã. Demonstraþie: Dacã graful admite douã componente distincte Ca ºi Cb, el nu este conex, a ºi b neputând fi legate printr-un lanþ. Dacã graful nu este conex, existã cel puþin douã vârfuri a ºi b care nu pot fi legate printr-un lanþ, deci Ca ºi Cb sunt douã componente distincte. Exemple de grafuri Harta cãilor ferate din þara noastrã reprezintã un graf în care nodurile de cale feratã reprezintã vârfurile grafului, iar legãturile directe pe cale aferatã reprezintã muchiile grafului. Cunoscând distanþele în kilometri, asociate fiecãrei muchii, ne putem pune problema gãsirii celui mai scurt traseu pe calea feratã între douã localitãþi. Aceasta va corespunde unui lanþ elementar, care uneºte cele douã localitãþi ºi pentru care suma distanþelor asociate muchiilor este minimã. Dacã ne propunem sã calculãm intesitãþile curenþilor care trec prin ramurile unei reþele electrice (fig.1), cunoscând schema reþelei electrice, tensiunile electromotoare ºi valorile rezistenþelor, se scriu legile lui Kirchoff relative la noduri ºi la ochiuri de reþea. Fãcând abstracþie de elementele de circuit care se gãsesc pe ramurile schemei putem desena aceastã reþea sub forma grafului din figura 2. Nodurile reþelei vor corespunde vârfurilor grafului, iar ochiurile de reþea vor corespunde ciclurilor elementare ale acestui graf. Fizicianul Kirchoff a studiat la mijlocul secolului trecut reþele electrice cu metode care aparþin astãzi teoriei grafurilor, contribuind la dezvoltarea acestei teorii.
Aceste formule de structurã au fost reprezentate sub formã de grafuri pentru care vârfurile sunt atomii (respectiv grupãrile) din moleculã, muchiile reprezentând legãturile lor chimice dupã cum urmeazã: Grafurile 3’b) ºi 3’c) nu sunt grafuri în sensul definiþiei date, deoarece între anumite perechi de vârfuri existã mai multe muchii. Un asemenea graf cu muchii multiple se numeºte multigraf. Într-un multigraf este desenul moleculei unei substanþe gradul unui vârf este tocmai valenþa atomului (grupãrii) respective. §2. Matricea asociatã unui graf Considerãm un p.graf G = (X, U) ºi fie x1 x2 ... xn vârfurile sale. Notãm cu aij numãrul arcelor lui U care pleacã de la xi la xj. Matricea pãtratã cu n linii ºi n coloane (aij) se numeºte matrice asociatã p-grafului G = (X, U) Vectorul ai = (ai1 ai2 ... ain) este al i-lea vector-linie, iar aj = (a1j, a2j, ... anj) este al j-lea vector-coloanã. Exemplu: X = {x1, x2, x3, x4, x5} Matricea asociatã este: µ §µ §
Fie A = (aij) o matrice asociatã unui p-graf, matricea sa transpusã A* = (aij*) se obþine din matricea A printr-o simetrie în raport cu diagonala principalã; aceasta va fi matricea asociatã p-grafului obþinut schimbând orientarea tuturor arcelor. Matricea sa complementarã A’ = (aij’) definitã prin µ § ; în cazul unui graf (X, Ã) matricea complementarã se obþine din A înlocuind cu 1 toþi coeficienþii ºi prin 0 toþi coeficienþii 1. Aceastã matrice A’ este asociatã grafului G’ = (X Ã’) definit prin: Ã’ = X-Ãx pentru µ § µ §.
Fie G = (X, Ã) un graf ºi A matricea sa asociatã. Matricea A este simetricã dacã ºi numai dacã graful G este simetric. Matricea A este asimetricã dacã ºi numai dacã graful G este antisimetric. Matricea A este completã dacã ºi numai dacã graful G este complet. Demonstraþia teoremei este evidentã.
Se considerã douã multigrafuri G = (X, U) ºi H = (X, V) având aceeaºi mulþime de vârfuri ºi matricele asociate A = (aij) ºi B = (Bij); matricea A+B corespunde multigrafului format prin reuniunea arcelor din U ºi V; matricea A·B corespunde multigrafului format astfel: de la vârful x la vârful y se duc atâtea arce câte drumuri distincte sunt care pleacã din x la y ºi sunt formate dintrâun arc din U urmat de un arc din V. În graful µ § numãrul arcelor care pleacã din xi spre xj este aij+bij; acest coeficient nu este altul decât coeficientul general al matricei A+B. Numãrul drumurilor distincte de forma µ § cu µ §, µ § este egal cu aik bkj; deci pentru a merge din xi la xj numãrul total al drumurilor distincte formate cu arcele din U urmate de arce din V este µ §, produs scalar al vectorului-linie ai ºi al vectorului coloanã bj; acest coeficient nu este altul decât coeficientul general al matricei AB. Corolarul 1 Dacã G este un p-graf ºi A matricea sa asociatã, coeficientul pij al matricei P = ëA este egal cu numãrul drumurilor distincte de lungime ë care pleacã din xi spre xj. Pentru ë = 1 teorema este trivialã, dacã presupunem teorema adevãratã pentru ë-1, ea rãmâne adevãratã pentru ë, deoarece Aë = A·Aë-1, ºi exprimã dupã teorema precedentã, numãrul drumurilor de lungime 1+(ë-1)=ë care pleacã din vârful xi spre vârful xj Corolarul 2 Într-un graf G existã un drum de lungime ë dacã ºi numai dacã µ §; nu existã circuite dacã ºi numai dacã µ § începând cu un anumit rang. Acest corolar rezultã imediat din corolarul 1. Aceste rezultate permit sã reducem la probleme de matrice un anumit numãr de probleme privind p-grafurile. Utilizarea practicã a descrierii unui graf prin matricea sa asociatã este evidentã când vrem sã numãrãm drumurile unui graf care satisfac anumite condiþii date.
Fie G = (X, U) un graf complet, antisimetric, ºi fie A = (aij) matricea asociatã dacã µ § este suma coeficienþilor liniei a i-a, atunci numãrul circuitelor de lungime 3 este: µ § Numãrul circuitelor de lungime 3 este: µ §. Un ciclu de lungime 3 nu este circuit dacã ºi numai dacã douã arce sunt identice cu-n acelaºi vârf xi spre exterior; deci numãrul total al ciclurilor de lungime 3, care nu sunt circuite, este exact µ § Observãm cã µ § de unde µ § µ §
µ § §3. Matrice de incidenþã Notãm prin u1, u2, ... un, arcele unui graf G = (X, U) ºi x1, x2, ... xn vârfurile sale ºi punem 1 dacã xi este extremitate iniþialã a lu uj sij = -1 dacã xi este extremitate finalã a lui uj 0 dacã xi nu este extremitate a lui uj Matricea S = (sij) se numeºte matrice de incidenþã a arcelor. Dacã u1, u2, ... un sunt muchiile grafului atunci punem rij =1 dacã xi este extremitate iniþialã a lu uj 0 în caz contrar Matricea R = (rij) este matricea de incidenþã a muchiilor. O matrice A = (aij) se numeºte total unimodularã dacã orice matrice pãtratã a lui A are determinantul egal cu 0, +1 sau -1, deoarece el este minor al matricei A de ordinul 1; sunt deci necesare criterii de recunoaºtere dacã o matrice formatã cu coeficienþii 0, +1, -1. este total unimodularã.
Matricea de incidenþã a arcelor este: µ § µ §
Aceste douã matrice sunt total unimodulare. Teoremã 1 (Heler ¨C Tompkins ¨C Gole) Fie A o matrice de coeficienþi 0, +1, -1, astfel încât fiecare coloanã sã conþinã cel mult doi coeficienþi nenuli; matricea A este total unimodularã dacã ºi numai dacã liniile sale se pot grupa în douã mulþimi disjuncte I1 ºi I2 astfel încât: 10 dacã doi coeficienþi nenuli din aceeaºi coloanã au acelaºi semn, atunci unul este în I1 ºi celãlalt în I2; 20 dacã doi coeficienþi nenuli din aceeaºi coloanã sunt de semne contrare, atunci amândoi sunt în I1 sau în I2. Demonstraþie: 10. Fie A o matrice ale cãrei linii pot fi împãrþite conform enunþului; orice matrice pãtratã B estrasã din A are de asemenea aceastã proprietate. Pentru a arãta cã matricea A este total unimodularã, este suficient sã arãtãm cã det(B) = 0, +1 sau -1. Aceastã propoziþie este adevãratã pentru matricele B de ordinul 1; presupunem verificatã pentru matricele de ordinul q-1 ºi sã deducem cã proprietatea este adevãratã pentru matrici pãtrate de ordinul q, ale cãror mulþimi disjuncte sunt I1 ºi I2. Dacã orice vector-coloanã bj are numai doi coeficienþi nenuli, avem: µ § Vectorii-linie nefiind liniari independenþi, avem atunci det(B) = 0. Dacã un vector-coloanã nu are coeficienþi nenuli, avem de asemenea det(B) = 0. În sfârºit, dacã existã un vector coloanã bj numai cu un singur coeficient nenul, fie bij = +1 sã notãm prin C matricea pãtratã dedusã din B suprimând linia i ºi coloana j; deoarece teorema este presupusã adevãratã pentru matricele de ordinul q-1, avem µ § sau 0. Propoziþia este adevãratã deci în toate cazurile. 20. Fie A o matrice total unimodularã astfel încât fiecare coloanã sã conþinã cel mult doi coeficienþi nenuli ºi sã arãtãm cã existã o partiþie (I1, I2) care sã verifice enunþul. Putem presupune cã fiecare coloanã care conþine un singur coeficient nenul poate fi suprimatã, fãrã sã afecteze enunþul Matricei A sã facem sã-i corespundã un graf G, neorientat, în modul urmãtor: liniei i îi asociem un vârf xi ºi coloanei j muchia uj; aceastã muchie va uni xk ºi xh dacã µ § ºi µ §. Vom spune cã o muchie uj este specialã dacã cele douã elemente ale vectorului coloanã aj au acelaºi semn. Sã arãtãm cã fiecare ciclu elementar al grafului conþine un numãr par de muchii speciale. În adevãr, dacã ar exista un ciclu elementar care nu ar avea aceastã proprietate, fie aceasta de exemplu µ § atunci sã considerãm determinantul submatricei corespunzãtoare: µ §
µ § Avem µ §, µ §; în consecinþã µ § pentru indici j corespunzãtori muchiilor nespecifice, care sunt în numãr de k - (2p+1). Dacã notãm prin µ § numãrul de inversiuni ale permutãrii µ § putem scrie: µ §
Corolarul 1 Într-un graf matricea de incidenþã a arcelor S = (sij) este total unimodularã. În adevãr, vectorul coloanã sj conþine coeficienþii 0, un coeficient +1 ºi unul -1. Putem atunci lua µ § ºi µ §
µ § ºi µ § GRAFURI PLANARE §1. Proprietãþi generale. Teorema lui Kuratovski. Definiþie 1. Un graf G = (X, U) este graf planar dacã el poate fi reprezentat pe un plan, aºa încât vârfurile sã fie puncte distincte, muchiile curbe simple ºi douã muchii sã nu se întâlneascã decât în extremitãþile lor. Reprezentarea lui G pe un plan conform cu condiþiile impuse se numeºte graf planar topologic ºi nu vom considera ca distincte douã grafuri planare topologice dacã le putem face sã coincidã prin deformarea elasticã a planului. Exemplul 1. Problema celor trei oraºe ºi a celor trei uzine. Fie trei oraºe a, b, c, pe care trebui esã le legãm prin conducte cu o uzinã de apã d, cu o uzinã de gaze e ºi cu o uzinã electricã f. Puntem plasa, pe un plan, cele trei oraºe, cele trei uzine ºi conductele, astfel încât douã conducte sã nu se întâlneascã decât la capete? Experienþa aratã cã putem plasa întotdeauna 8 conducte, iar cea de-a 9-a taie întotdeauna una din cele 8. (fig.1) fig.1
(apã) (gaz) (electricã)
Fie G = (X, U) un graf planar topologic; o faþã a lui G este o regiune a planului limitatã de muchii ºi astfel încât douã puncte arbitrare din aceastã regiune pot fi unite printr-o linie continuã care nu întâlneºte nici muchii, nici vârfuri. Vom nota mulþimea feþelor cu Z, o faþã cu z, iar frontiera unei feþe z este mulþimea muchiilor care ating faþa z. Douã feþe z ºi z’ se zic adiacente dacã frontierele lor au o muchie comunã însã douã feþe care se ating doar într-un vârf nu sunt adiacente. Într-un graf topologic, frontiera unei feþe z este formatã din unul sau mai multe cicluri elementare disjuncte, de muchii suspendate sau care unesc douã cicluri disjuncte (istmuri). Se numeºte contur al unei feþe z, conturul ciclurilor sale elementarecare conþin în interiorul lor toate celelalte mucii ale frontierei. Existã întotdeauna o faþã nelimitatã ºi numai una pe care o numimfaþã infinitã ºi care nu are contur. Toate celelalte feþe sunt feþe finite ºi admit contur.
Într-un graf planar topologic G, contururile diferitelor feþe finite constituie o bazã fundamentalã de cicluri independente. Teorema este adevãratã dacã G are douã feþe finite; presupunem teorema adevãratã pentru orice graf cu (f-1) feþe finite ºi arãtãm plecând de aici cã teorema este adevãratã pentru un graf planar topologic G cu f feþe finite. Presupunem cã contururile nu ar fi toate cicluri disjuncte (în sensul muchiilor), caz în care teorema de demonstrat ar fi evidentã. Putem atunci, suprimând o muchie u, sã obþinem un graf G cu f-1 feþe finite, ale cãror contururi constituie o bazã fundamentalã de cicluri independente. Repunând muchia u se creeazã o nouã faþã finitã al cãrei contur este un ciclu independent de cele precedente ºi conþine o muchie pe care celelalte nu o au. Dar adunarea unei muchii nu poate mãri decât cu o unitate numãrul ciclomatic, deci rezultã cã feþele finite ale lui G determinã o bazã fundamentalã de cicluri independente. Corolarul 1 Dacã într-un graf planar topologic conex existã n vârfuri, m muchii ºi f feþe, atunci avem n ¨C m + f = 2 (formula lui Euler). Numãrul finit este egal cu numãrul ciclomatic v de unde: µ §
Într-adevãr, în graful planar topologic corespunzãtor, fiecare faþã este înconjuratã de cel puin trei muchii distincte. Dacã se formeazã graful simplu de incidenþã faþã ¨C muchii , atunci numãrul arcelor este µ § pe deoparte ºi µ § pe altã parte. Deci µ §. Rezultã cã µ § ºi deci µ §. Dacã fiecare vârf este extremitate a cel puþin 6 muchii, atunci se obþine, în acelaºi mod, µ §, deci, dupã formula lui Euler, avem: µ § ceea ce este absurd. Formula lui Euler este utilãîn anumite împrejurãri. Exemplul 1 Fie un poliedru conex cu n vârfurim m muchii ºi f feþe, din spaþiul cu trei dimensiuni. Putem sã reprezentãm acest poliedru pe o sferã, aºa încât douã muchii sã nu se taie dcât la extremitãþi; efectuând apoi o proiecþie steriograficã al cãrei centru va fi în mijlocul unei feþe, îl putem reprezenta pe un plan. Graful fiind planar, se obþine o relaþie fundamentalã a poliedrelor conexe ºi anume: µ §. Exemplul 2 Arãtãm, cu ajutorul formulei lui Euler, cã graful celor 3 oraºe ºi 3 uzine nu poate fi un graf planar. Presupunând cã ar fi planar, am aveaµ §. Fiecare faþã are cel puþin 4 muchii în conturul sãu (deoarece dacã o faþã s nu ar avea decât 3 muchii, ea ar fi mãrginitã de 3 vârfuri, dintre care 2 aparþin aceleiaºi categorii: oraºe sau uzine; ori douã vârfuri din aceeaºi categorie nu pot fi adiacente). Dacã se formeazã graful simplu de incidentã feþe ¨C muchie, atunci numãrul de arce este µ § pe deoparte ºi µ § pe de altã parte, deci: µ § c.c. e absurd. Exemplul 3 Arãtãm cã graful complet cu 5 vârfuri nu este planar. Presupunând cã acest graf ar fi planar, am avea µ § ceea ce este absurd, pentru cã µ § ºi fiecare faþã are cel puþin 3 muchii în conturul sãu. Dacã se formeazã graful simplu de incidenþã feþe ¨C muchii, atunci numãrul de arce este µ § pe deoparte ºi µ § pe de altã parte, ceea ce conduce la; µ §. Exemplele 2 ºi 3 ne permit sã definim o categorie de grafuri neplanare ºi anume de tip1 ºi de tip2, grafuri în care putem adãuga pe fiecare muchie aâte vârfuri vrem ºi obþinem alte grafuri neplanare. Aceastã observaþie are o reciprocã care este teorema lui Kuratovski. Dacã ì este un ciclu elementar, cãruia îi asociem în mod arbitrar un sens, ºi dacã a ºi b µ §, atunci notãm prin µ § secvenþa vârfurilor lui ì întâlnite mergând de la a spre b în sensul pozitiv inclusiv a ºi b. graf de tip 1. graf de tip 2. Dacã G este un graf cu o mulþime de articulaþii A, se numeºte piesã a grafului G, relaþivã la A, o componentã conexã C a subgrafului generat de X-A, împreunã cu muchiile incidente cu C ºi extremitãþile lor. Teorema lui Kuratovski Condiþia necesarã ºi suficientã pentru ca un graf G sã fie planar, este ca el sã nu admitã subgrafuri parþiale de tip 1 sau de tip 2. Demonstraþie: Am vãzut cã un graf care admite un subgraf parþial de tip 1 sau de tip 2 nu este planar; invers arãtãm cã un graf G care nu admite subgrafuri parþiale de tip 1 sau de tip 2 este planar. Dacã G are una, douã sau trei muchii, enunþul este adevãrat. Presupunem enunþul adevãrat pentru orice graf cu mai puþin de m muchii ºi arãtãm cã el rãmâne adevãrat pentru un graf cu m muchii. Fie G un graf cu m muchii care nu admite subgrafuri de tip 1 sau de tip 2 ºi este neplanar. Acest graf este conex pentru cã, dacã nu ar fi aºa, componentele sale fiind planare, G ar fi planar. De asemenea, acest graf va fi nearticulat, deoarece, dacã un nu ar fi aºa, piesele lui G relative la punctul de articulaþie a, fiind planare, pot fi reprezentate planar astfel încât punctul de articulaþie a sã fie pe feþele lor infinite ºi G ar fi planar. 10. Sã arãtãm cã, dacã scoatem din G o muchie µ §, mai rãmâne un ciclu elementar ì care trece prin a ºi b. Dacã nu ar fi aºa, atunci graful G’ obþinut din grafull G prin suprimarea muchiei µ § ar fi articulat, dupã teorema lui Menger, deci vârfurile a, b, relativ la punctul de articulaþie c vor fi pe douã piese distincte Ca ºi Cb. Graful Ca’ obþinut plecând de la Ca adãugându-i muchia µ § este planar, deoarece nu conþine grupuri de tip 1 sau de tip 2. Putem deci, fãcând o proiecþie steriograficã, sã-l reprezentãm planar pe Ca’ astfel încât muchia µ § sã fie conturul feþei infinite. La fel procedãm cu Cb’, deci muchia µ § adãugatã la Cb va fi pe conturul feþei infinite. unind apoi pe a cu b se obþine un graf planar care conþine pe G de unde rezultã contradicþia. 20. Sã considerãm în graful planar topologic G’ obþinut prin suprimarea muchiei µ § un ciclu elementar ì care trece prin a ºi b ºi înglobeazã în interiorul sãu cel mai mare numãr de feþe. Dându-i lui ì o orientare arbitrarã, ì împarte planul în douã regiuni ºi piesele lui G’ având vârfurile lor în interior (respectiv exterior) vor fi numite piese interioare (respectiv piese exterioare). O piesã exterioarã nu poate conþine mai mult de un vârf din µ §, deoarece altfel am putea construi un ciclu ì care sã înglobeze în interiorul sãu un numãr mai mare de feþe; precum ºi din µ § o piesã exterioarã nu întâlneºte ì decât în unul sau douã puncte. Existã cel puþin o piesã exterioarã ºi o piesã interioarã care întâlnesc în acelaºi timp µ § ºi µ §, deoarece nu putem trasa planar muchia µ §. 30. Sã arãtãm cã existã o piesã interioarã C ºi o piesã exterioarã D care întâlnesc pe µ § ºi pe µ §, astfel încât punctele de contact c ºi d ale lui D cu ì ºi punctele de contact e ºi f ale lui C cu ì sunt pe ì într-o ordine alternatã: c, e, d, f. Dacã presupunem cã nu ar fi aºa, fie C1 o piesã interioarã care întâlneºte pe µ § ºi µ § ºi fie e1 ºi f1 douã puncte de contact consecutive pe ì. Se poate desena o linie continuã v care sã uneascã e1 ºi f1 în interiorul lui ì ºi care sã nu întâlneascã nici o muchie existentã (deoarece prin ipotezã nu existã piese exterioare care sã întâlneascã) µ § ºi µ §. Orice piesã interioarã care întâlneºte numai µ § poate fi transferatã în exterior pe faþa limitatã de v ºi ì, aceasta este tocmai cazul pentru piesa C1. Va rãmâne cel puþin o piesã interioarã C2 care nu poate fi transferatã, deoarece a ºi b ar putea fi unite planar, ºi aceastã piesã are douã puncte de contact consecutive e2 ºi f2 pe µ §, cel puþin unul fiind pe µ §. Vom continua acelaºi procedeu de transfer cu C2 în loc de C1 etc.; acest procedeu nu se va opri niciodatã ºi avem o contradicþie deoarece graful este finit. Notãm cu e, f, g, ºi h punctele de contact ale lui C ºi ì care verificã relaþiile µ §, µ §, µ § ºi µ §. Evident µ § ºi µ §, însã am putea avea e = g ºi e = h. 40. Dacã vârfurile e ºi f sunt unul pe µ § ºi celãlalt pe µ §, atunci vom putea pune de exemplu e = g, f = h, ºi se vede imediat cã G conþine un graf de tip 1, ceea ce este contrar ipotezei nostre (fig.3.a). fig.3.a
fig.3.b 50. Dacã vârfurile e ºi f sunt ambele pe µ § putem presupune h = c, deoarece dacã µ §, µ § atunci regãsim una dintre figurile eliminate în cazul 40. obþinem un graf care conþine un graf de tip 1, ceea ce este absurd. Din aceleaºi motive vom înlãtura cazul în care e ºi f sunt ambele pe µ § (fig.3.c). 60. Dacã e = a, µ §, fie exemplul µ §, atunci se obþine figura (3.c) care conþine un graf de tip 1 ceea ce este absurd.
dacã lanþurile lui C care unesc cd ºi ef au mai mult de un vârf comun, atunci se obþine figura (3.d) care conþine un graf de tip 1, ceea ce este absurd. dacã lanþurile lui C care unesc cd ºi ef au un singur vârf comun, atunci se obþine figura (3.e) care conþine un graf de tip 2, ceea ce este de asemenea absurd. Toate poziþiile lui e ºi f fiind examinate, graful G, aºa cum a fost definit mai înainte, nu poate exista. Deci, teoria este demonstratã. §2. Funcþiile lui Grundy. Numãr cromatic; clasã cromaticã. Fie graful G = (X, U), o funcþie µ § se numeºte funcþie a lui Grundy pe graful respectiv dacã g(x) µ § Deci din µ § (1) Funcþiile Grundy sunt folosite ºi pentru grafuri finite ºi pentru grafuri infinite.
Evident, deoarece vârful cãruia îi este ataºatã bucla se precede pe sine însuºi ºi µ § este o absurditate. Propoziþie 2 Dacã un graf G nu are bucle ºi nici circuite, atunci el admite o funcþie a lui Grundy ºi numai una.
Fie µ § (2) nivelele ce se obþin când ordonam graful prin eliminarea succesivã a descendenþilor. Din relaþia (1) rezultã µ § ºi deci µ § (3). Definiþia funcþiei Grundy ne dã µ § (4) Pentru vârfurile din Nr obþinem: 1 dacã µ § g(x) = 2 dacã µ § 3 dacã µ §
Acest graf admite funcþia lui Grundy ale cãrei valori sunt notate în vârfuri ºi este evident o funcþie ordinalã. Exemplul 2 Considerãm graful fãrã bucle ºi fãrã circuite din figura Partiþia în nivele a vârfurilor sale, obþinutã prin eliminarea succesivã a descendenþilor este datã de: 1234567891011IIIIIIIVVVIVIIVIIIIX1111333333310211222221103111111104112221110511222106111107112222108111091121010110110 Redesenez graful cu ordonarea ce rezultã din tabel pentru vârfuri, lângã care sunt înscrise valorile funcþiei lui Grundy ce se obþine imediat în baza definiþiei acesteia. Propoziþie 3 Grafurile formate dintr-un singur circuit admit funcþii Grundy dacã ºi numai dacã el are o lungime parã.
Suprimând un arc al circuitului, rezultã un drum ì. Fie µ § ºi µ § primul ºi ultimul vârf al drumului , cum drumul este un graf secvenþial, în acesta avem: µ § ºi µ § dacã µ § este par (1) ºi µ § ºi µ §dacã µ § este impar (2). Reintroducând apoi arcul µ § constatãm cã (2) contrazice definiþia funcþiei Grundy, pe când (1) nu. Deci în graful dat funcþia Grundy coincide cu cea obþinutã de-a lungul drumului, dacã circuitul are un numãr par de arce ºi nu existã dacã acest numãr e impar.
Observaþie 1 Propoziþia 3 ºi corolarul sãu se extind de la sine la grafurile care conþin un singur circuit. Singurul lucru care se schimbã în raþionamentul de mai sus este cã µ § nu mai are obligatoriu valoarea 1. Exemplul 3 Fie graful: are un singur circuit de lungime 2. Suprimând arcul µ § se obþine graful fãrã circuite de mai jos
Observaþie 2. Din propoziþia 3 nu rezultã cã, dacã un graf conþine circuite de lungime imparã, el nu admite funcþii Grundy. Exemplul 4 Fie graful cu douã circuite din care unul de lungime 3 ºi admite totuºi funcþia Grundy ale cãrei valori sunt notate în vârfuri. Ea s-a obþinut suprimând arcul µ § comun ambelor circuite, ceea ce conduce la graful urmãtor. Reintroducerea arcului suprimat nu contrazice definiþia funcþiei lui Grundy, deci cea gãsitã în graful fãrã circuite este admisã ºi de graful dat. Observãm însã pe figurã cã deschizând circuitele prin înlãturarea arcului µ § nu se obþine o soluþie Pentru cãutarea funcþiei Grundy în grafurile cu circuite ne putem folosi de urmãtorul algoritm: Deschidem toate circuitele, suprimând arce care le sunt comune ºi pe care le alegem astfel încât în extremitãþile lor terminale circuitele sã se despartã fãrã a rupe conexiunile grafului. Este recomandabil ca numãrul arcelor elementare sã fie cât mai mic. Cãutãm funcþia lui Grundy µ § în graficul parþial astfel obþinut. Reintroducem arcele suprimate; dacã în extremitãþile lor µ § are valori distincte, atunci µ § este o funþie Grundy pentru graful dat. Exemplul 5 Fie graful Suprimând în graful dat arcele µ § ºi µ § se obþine graful fãrã circuite În acesta avem µ § ºi µ § deci am gãsit ºi o funcþie Grundy a grafului cu circuite. Soluþia nu este unicã: prin eliminarea din graful dat a arcelor µ § ºi µ § se gãseºte un alt graf parþial fãrã circuite ºi funcþia xx1x2x3x4x5x6x7x8x9x10x11µ §42133121231 Pentru grafurile neorientate funcþia Grundy se defineºte cerând sã se ataºeze fiecãrui vârf cel mai mic numãr natural distinct de cel din vârfurile adiacente. Proprietãþile ce urmeazã sunt imediate: Orice graf conex neorientat admite cel puþin douã funcþii Grundy, ele se pot construi inclusiv în cazul arborilor ¨C începând de la orice µ § pentru care luãm µ §. Orice arbore admite cel puþin o funcþie Grundy cu valorile din mulþimea µ § cãci totdeauna putem lua µ § unde µ § este rãdãcina. Numãrul µ § poate diferi de la o funcþie Grundy la alta în acelaºi graf. În legãturã cu aceasta se poate cere maximul ºi minimul lui p pe mulþimea tuturor funcþiilor lui Grundy pe care le admite un graf neorientat. Este evident µ §. Toate funcþiile Grundy dintr-un graf neorientat, dar complet au acelaºi p ºi avem p = # X Orice graf neorientat care nu conþine cicluri de lungimi impare admite cel puþin o funcþie Grundy cu valori în µ §. Grafurile neorientate care conþin circuite de lungimi impare au µ § pentru oricare dintre funcþiile lui Grundy pe care le admit. §3.Numãr cromatic; clasã cromaticã
Legãtura dintre funcþiile Grundy corespunzãtoare lui G ºi numãrul cromatic a lui G este evidentã în baza propoziþiei 3) din paragraful precedent. Dacã asociem câte o culoare fiecãreia dintre cele p valori pe care le ia o anumitã funcþie Grundy a grafului, acesta devine p-cromatic, iar µ §. Deci avem µ §. Cum µ § ne întrebãm care e condiþia necesarã ºi suficientã ca µ §. Este evident cã oricare arbore se bucurã de aceastã proprietate. Propoziþia 1 (Kõning) Un graf neorientat are numãrul cromatic 2 dacã ºi numai dacã nu are cicluri de lungime imparã. Demonstraþie Dacã G nu conþine cicluri de lungime imparã din propoziþia 5, rezultã cã µ §. Dacã în G existã mãcar un ciclu de lungime imparã, atunci se aplicã proprietatea 6 ºi deci µ §. Observaþie: E suficientã lipsa ciclurilor elementare de lungime imparã pentru ca teorema lui Kõning sã se aplice, cãci celelalte se desfac în cicluri elementare dintre care mãcar unul este obligatoriu de lungime imparã. Propoziþie 2 Orice graf neorientat care admite o funcºie Grundy cu valorile 1, 2, ... p este p-cromatic. E suficient sã înlocuim fiecare din cele p valori cu câte o culoare. Din definiþia funcþiei Grundy rezultã atunci cã orice vârfuri adiacente vor fi colorate diferit. Deci, pentru ca un graf sã fie p-cromatic e suficient ca el sã admitã o funcþie Grundy cu p valori. Procedând invers, adicã asociind celor p culori dintr-un graf p-cromatic numerele 1, 2, ... p, nu se obþine întotdeauna o funcþie Grundy. Explicaþia o dã proprietatea urmãtoare. Propoziþia 3 Funcþiile lui Grundy ce se pot deduce din p-cromatismul unui graf au cel mult p valori. Fie µ § partiþia mulþimii X a vârfurilor unui graf p-cromatic, dupã culoarea lor. Trecem la o nouã partiþie µ §. Submulþimile µ § (cu µ §) le formãm iterativ, astfel: µ § include pe X1 reunit succesiv cu vârfurile : a) µ § neadiacente cu cele din X1; b) µ § neadiacente cu cele din X1 ºi cu cele de la a); c) µ § neadiacente cu cele din X1 ºi cu cele de la a) ºi b); ............................................................................................... . µ § include pe µ § completat succesiv cu vârfurile: á) µ § neadiacente cu cele din µ § â) µ § neadiacente cu cele din µ § ºi cu cele din á). µ § conþine pe µ § Fie r cel mai mare indice al submulþimii µ § nevide, astfel obþinute µ §. Funcþia g(x) definitã prin µ § µ § este evident o funcþie Grundy în graful dat.
Pornind de la cromatismul grafului cãutãm ca în demonstraþia de mai sus, funcþiile Grundy. Sã adoptãm ordinea v ¨C a ¨C n ¨C r ºi rezultã µ §; µ §; µ § ºi µ §. Obþinem µ § µ § µ §
µ § Gãsim urmãtoarea funcþie Grundy: xx1x2x3x4x5x6x7x8x9x10x11x12µ §231112322132 Cum în graf existã cicluri de lungime imparã, înseamnã cã, pentru mulþimea vârfurilor sale, funcþiile lui Grundy nu pot lua mai puþin 3 valori, rezultã µ §. Propoziþia 4. O condiþie necesarã ºi suficientã pentru µ § este ca graful sã nu admitã funcþii Grundy cu mai puþin de s valori. Clasa cromaticã a unui graf neorientat este cel mai mic numãr de culori ce pot fi atribuite muchiilor sale astfel încât orice muchii adiacente sã fie colorate diferit. Problema determinãrii clasei cromatice a unui graf este echivalentã cu aceea a gãsirii numãrului cromatic al altuia, care se deduce astfel din cel dat: muchiile grafului dat se reprezintã prin vârfuri în cel transformat; douã vârfuri din al doilea graf se unesc printr-o muchie dacã ºi numai dacã muchiile respective sunt adiacente în cel iniþial. Presupunem cã am adoptat aceeaºi numerotare pentru cele cinci vârfuri ca ºi pentru culorile lor ºi cã vârfurile sunt dispuse în jurul lui x în ordinea numerotãrii. Fie G1,3 subgraful ale cãrui vârfuri sunt colorate cu c1 ºi cu c3. Dacã a1 ºi a3 aparþin unor componente diferite ale lui G1,3 permutãm între ele culorile c1 ºi c3 în componenta ce conþine pe a, deci a1 va fi coloratã în 3 ºi deci lui xi se poate da culoarea lui c1. Dacã a1 ºi a3 aparþin aceleiaºi componente în G1,3 atunci a2 ºi a4 sunt obligatoriu în componente diferiteale subgrafului G2,4, altfel G nu ar fi planar, ºi se repetã cele de mai sus în G2,4 deci x poate fi colorat cu c2. Din propoziþia de mai sus rezultã doar cã toate grafurile planare conexe au µ §, dar nu ºi µ §. Se presupune cã µ §, supoziþie care poartã numele de conjunctura celor patru culori întrucât practica o confirmã, dar nu a putut fi încã demonstratã. Existã grafuri planare cu µ §. Conjunctura celor patru culori se referã la mulþimea tuturor grafurilor planare. Propoziþia 2 (teorema lui Heowood) Într-un graf planar G, conex ºi fãrã istmuri, ale cãrui vârfuri au toate gradul 3, dacã una din proprietãþile urmãtoare e adevãratã, atunci sunt toate adevãrate. Feþele lui G pot fi distinctiv colorate cu 4 culori; Muchiile lui G pot fi distinctiv colorate cu 3 culori; Fiecare vârf x poate fi etichetat cu un numãr p(x) egal cu +1 sau -1, astfel ca de-a lungul conturului ì al oeicãrei feþe sã avem: µ § mod 3 (*)
Demonstraþie µ § Fie µ § cele patru culori ale feþelor 1, 2, 3, culorile pe care le vom folosi pentru muchii. Colorãm cu 1 muchiile ce separã pe c1 de c2 ºi pe cele dintre c3 ºi c4. Apoi folosim: Yüklə 175,66 Kb. Dostları ilə paylaş:
|