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
§4. Cromatismul grafurilor planare
Yüklə 175,66 Kb.
|
| §4. Cromatismul grafurilor planare.
Primele probleme legate de cromatismul grafurilor planare au fost cele de colorare a hãrþilor geografice. Luãm pe harta e reprezintã împãrþirea administrativ-teritorialã, care este un graf planar, câte un punct situat în interiorul feþelor finite. Considerãm aceste puncte drept vârfuri într-un nou graf. Între douã vârfuri trasãm o muchie dacã ºi numai dacã feþele din graful iniþial pe care ele le reprezintã sunt adiacente. Noul graf este evident tot planar ºi se numeºte dualul celui dat. dacã vrem sã colorãm distinctiv subîmpãrþirile teritoriale ale hãrþii, feþele adiacente trebuie sã aibã culori diferite. Problema determinãrii numãrului minim de culori necesare revine, aflãrii numãrului cromatic al grafului dual. Principalul rezultat obþinut în aceastã privinþã este dat de propoziþia: Propoziþia 1 Orice graf planar ºi conex cu cel puþin 5 vârfuri este 5-cromatic. Demonstraþie Pentru # X = 5, propoziþia este o tautologie. Deci, dacã vom demonstra pentru cazul #X = n prin inducþie matematicã, atunci propoziþia va fi valabilã pentru orice # X. Fie G un graf planar cu n vârfuri ºi x un vârf al sãu cu µ §. Suprimând acest vârf, subgraful rãmas este 5-cromatic (din presupunerea fãcutã în inducþie). Deci îi putem colora vârfurile cu culorile µ §. Dacã µ §, pentru x poate fi disponibilã cel puþin una din aceste culori. Dacã µ § ºi printre vârfurile adiacente cu x, µ § sunt cel puþin douã cu aceeaºi culoare, de asemenea putem folosi una din culorile neutilizate atribuind-o lui x. Rãmâne cazul µ § în ipoteza cã toþi ai sunt distincþi coloraþi. Pe coloana muchiilor ce despart pe c1 de c3 ºi c2 de c4 ºi atribuim pe 3 muchiilor ce despart pe c1 de c4 ºi c2 de c3 (fig.1). rezultã o colorare diferitã a muchiilor adiacente, cãci altfel ar exista feþe adiacente identic colorate. Demonstrãm µ § Graful parþial G1,2 cu muchile colorate 1 ºi 2 este planar ºi are toate vârfurile de gradul 2 (fig.2). Deci acest graf are o faþã finitã á ºi o faþã infinitã â. La fel pentru G1,3 ale cãrui feþe le etichetãm cu ã ºi ä (fig.3). Prin suprapunerea lui G1,2 cu G1,3 pe feþele lui G se obþin 4 combinaþii (fig.4) pentru care luãm µ §, µ §, µ §, µ § sau orice altã permutare a culorilor ci. Douã feþe adiacente nu pot fi la fel colorate fãrã sã fie contrazisã ipoteza. Demonstrãm µ § Adoptãm un sens de rotaþie în plan notat cu +, iar sensul contrar îl notãm cu -. Punem µ § când muchiile incidente în x ºi colorate în 1, 2, 3 se succed în sensul + ºi µ § în caz contrar (fig.5) (în figurã sensul + este sensul trigonometric). Parcurgem în sensul + conturul ì al unei feþe pornind de la o muchie oarecare. Când trecem printr-un vârf marcat cu -1, culorile muchiilor ciclului pe care acest punct le separã se succed în sensul sãgeþii prin permutarea circularã (µ §), pe când la trecerea prin vârful x cu p(x) = +1 ele se permutã în sens invers. Deci, când ajungem din nou la muchia iniþialã, suma algebricã (x) va fi în mod necesar un multiplu de 3. Demonstrãm µ § Evident, cãci putem aplica de-a lungul fiecãrui contur procedeul de mai sus, trecând de la marcajul dat al vârfurilor, la colorarea arcelor. la închiderea conturului nu poate surveni o contradicþie decât dacã marcajul vârfurilor nu satisface condiþia (x). Oricãrei etichetãri a vârfurilor care satisface condiþia (x) îi corespund trei posibilitãþi de colorare a arcelor, dupã cum afectãm arcului iniþial pe 1, 2 sau 3. Cele trei soluþii se deduc una din alta prin permutarea circularã a culorilor. Pentru grafurile planare, conexe ºi fãrã istmuri, ale cãror vârfuri au toate gradul 3, din propoziþia 2 decurg corolarele: Corolarul 1 Când numãrul muchiilor conturului oricãrei feþe este un multiplu de 3, e posibilã colorarea feþelor cu 4 culori. Corolarul 2 Când numãrul muchiilor conturului oricãrei feþe este un multiplu de 2, e posibilã colorarea feþelor cu 4 culori. Problema 1 Fie douã grafuri µ § ºi µ § având aceeaºi mulþime de vârfuri ºi B B’ matricele asociate corespunzãtor. Sã se verifice: matricea B+B’ corespunde grafului µ § matricea B·B’ corespunde grafului definit astfel: de la un vârf j se duc atâtea arce câte drumuri distincte sunt, care pleacã dintr-un arc U urmat de un arc din V.
Rezolvare: Matricea B+B’ corespunde grafului µ §, iar matricea B·B’ corespunde grafului reprezentat dupã enunþul b) din problemã, figurate mai jos: Matricele sunt: µ § µ §
µ § µ § Problema 1’ Fie o mulþime µ §. În mulþimea X se defineºte o aplicaþie à prin urmãtoarea corespondenþã: µ § Se cere sã se reprezinte graful µ § Rezolvare: Considerãm cã elementele mulþimii X sunt vârfurile grafului, aplicaþia definitã în enunþul exerciþiului defineºte complet graful µ §. Pentru aceasta, vom defini arcul (a,b) dacã ºi numai dacã µ §, dupã cum se vede în figura de mai jos.
Problema 2 Fie graful µ § reprezentat mai jos. Sã se determine închiderea tranzitivã a acestui graf. Prin definiþie închiderea tranzitivã a grafului µ § este tot un graf µ §, obþinut din graful dat, unde à este o aplicaþie a lui X în X, care asociazã fiecãrui vârf x o submulþime a lui X formatã din x ºi din toate vârfurile accesibile din x prin drumuri posibile din graful G. Cu alte cuvinte, pentru x din X avem µ § unde µ §, µ § Avem: µ § µ § µ § µ § µ § de unde rezultã µ §
Rezolvare: Prin definiþie o funcþie g definitã pe mulþimea X este o funcþie Grundy, dacã orice valoare a sa este un întreg pozitiv sau zero ºi g(x) este cel mai mic întreg pozitiv care nu aparþine mulþimii µ §. Altfel spus, funcþia g definitã pe mulþimea X este o funcþie Grundy dacã: (1) µ § µ § cu µ § (2) µ §
Pentru determinarea valorilor funcþiei g folosim urmãtorul algoritm: Presupunem submulþimea µ § din definiþia funcþiei Grundy pentru orice µ § g(x) = 0; Pentru orice x din µ § luãm g(x)=1; Procedãm din aproape în aproape, determinãm submulþimea µ § ºi pentru orice x din Xi, vom lua µ § ºi µ §. Pentru un graf dat, funcþia Grundy dacã existã, nu este obligatoriu sã fie unicã. Pentru graful dat avem: a) µ § pentru cã µ §; deci µ § b) µ § pentru cã µ § dar µ § deci µ § µ §
c) µ § pentru cã µ §
Deci d) µ §
cãci µ § ºi µ §, deci µ §
e) µ § cãci µ §, deci µ §
Deci valorile funcþiei Grundy pentru graful dat sunt: µ §
µ § pentru care µ § µ § pentru care µ § µ § pentru care µ § care sunt clase de echivalenþã determinate de relaþia µ § III. POLIEDRE CONVEXE
Observaþii: Figura 1a reprezintã o mulþime convexã, iar figura 1b reprezintã o mulþime neconvexã. Mulþimea vidã ºi mulþimea formatã dintr-un singur punct sunt mulþimi convexe. Mulþimea formatã din douã puncte distincte nu este convexã.
Orice intersecþie de mulþimi convexe este convexã. Fie M1, M2 ... Mn ... mulþimi convexe. Notãm cu µ § ºi fie µ § µ § µ §este mulþime convexã. Interiorul unghiului propriu µ § este mulþimea de puncte µ § unde µ § ºi µ § (fig.2). Proprietãþi Planul ºi orice dreaptã sunt mulþimi convexe; Orice segment ºi orice semidreaptã sunt mulþimi convexe; Semiplanele deschise ºi semiplanele închise sunt mulþimi convexe; Înteriorul unui unghi µ § este o mulþime convexã, fiind intersecþia a douã semiplane deschise care sunt convexe; Dacã interiorul unui triunghi ABC se defineºte astfel µ § unde µ §, µ §, µ § atunci µ § este o mulþime convexã. O linie poligonalã este o mulþime de forma: µ §, unde punctele µ § se numesc vârfurile liniei L, iar segmentele µ § se numesc laturile ei; laturile µ § ºi µ § se zic vecine (fig.3a). Linia poligonalã închisã este linia poligonalã pentru care µ § (fig.3b), ºi simplu închisã dacã în plus orice douã laturi vecine nu au punct comun ºi douã laturi vecine au suporturi diferite.
O linie poligonalã simplu închisã se numeºte poligon. Figura 3b nu este poligon pentru cã un poligon nu se autointersecteazã. Denumirea poligonului se dã în funcþie de numãrul de laturi pe care le are. Segmentele PiPK care nu sunt laturi se numesc diagonale. Poligonul cu vârfurile P1,P2,P3, ... Pn va fi notat cu P1P2...Pn. Poligonul P1P2...Pn se numeºte convex, dacã pentru fiecare laturã µ §, toate vârfurile diferite de Pk ºi PK+1 se gãsesc de aceeaºi parte a dreptei PkPK+1, pentru µ § ºi µ § (fig.3c). Interiorul unui poligon convex este intersecþia semiplanelor deschise limitate de suporturile laturilor poligonului ºi care conþine vârfurile nesituate pe laturile respective (fig.4a). Dacã notãm µ § pentru µ § ºi µ § atunci µ §. Reuniunea dintre poligonul convex P1P2...Pn ºi µ § se numeºte suprafaþã poligonalã convexã. Se numeºte suprafaþã poligonalã o mulþime de puncte din plan care este reuniunea unui numãr finit de suprafeþe poligonale convexe, acestea având douã câte douã interioare disjuncte. (fig.4b) Dacã S este o suprafaþã poligonalã ºi [L1] [L2] ¡K [LK] sunt suprafeþele poligonale convexe respective, adicã µ § ºi µ § pentru µ §, atunci vom spune cã mulþimea µ § constituie o descompunere a suprafeþei poligonale S (fig.4c). Pentru suprafaþa poligonalã convexã µ § poligonul µ § se numeºte frontierã. Un punct P al unei suprafeþe poligonale S se numeºte punct interior al lui S dacã existã un disc cu centrul s inclus în S. Punctele lui S care nu sunt interioare lui S sunt puncte frontierã pentru S ºi formeazã frontiera lui S. Din definiþie rezultã cã orice suprafaþã poligonalã se descompune în suprafeþe poligonale convexe. Teoremã O suprafaþã poligonalã convexã cu n-laturi (µ §) se descompune în n-2 suprafeþe triunghiulare. Demonstraþie Se considerã poligonul convex µ § ºi dreapta P1P3, o dreaptã care nu este suportul unei laturi a lui L are cel mult douã puncte comune cu L, deci dreapta P1P3 intersecteazã poligonul L numai în P1 ºi P3. Deci punctele P4P5¡KPn sunt de aceeaºi parte a lui P1P3, deci P1P3 P4¡KPn este un poligon convex. Deoarece P3 se aflã în interiorul P2P1Pn rezultã cã P2 ºi Pn se aflã de o parte ºi de alta a dreptei P1P3. Deci punctele P2 ºi P4, P5¡KPn se aflã în semiplane opuse faþã de P1P3, adicã interiorul triunghiului P1P2P3 ºi interiorul poligonului P1P3 P4¡KPn se aflã în semiplane opuse, având intersecþia vidã ºi µ §. Dacã aplicãm succesiv rezultatul obþinut mai sus pentru suprafeþele poligonale µ §, µ § etc, care au fiecare cu o laturã mai puþin decât precedenta ºi astfel obþinem rezultatul cerut de teoremã, figura 5. Consecinþã : Orice suprafaþã poligonalã poate fi descompusã în triunghiuri ºi descompunerea nu este unicã. §2. Mulþimi poliedrale Mulþimile poliedrale constituie analogul suprafeþelor poligonale din plan, cu deosebirea cã în acest caz suprafeþele poligonale convexe sunt înlocuite cu prisme, piramide ºi trunchiuri de piramidã. Se numeºte mulþime poliedralã o mulþime de puncte din spaþiu care este reuniunea unui numãr finit de prisme, piramide ºi trunchiuri de piramidã, acestea având douã câte douã interioare disjuncte. Dacã P este mulþimea poliedralã, iar µ § sunt prismele piramidale ºi trunchiurile de piramide respective, adicã µ § ºi µ §, µ §, atunci se va spune cã mulþimea P se descompune în mulþimile µ §. Un punct O al mulþimii poliedrale P se numeºte punct interior al lui P dacã existã un corp sferic cu centrul în O inclus în P. Punctele mulþimii P ce nu sunt interioare acesteia se numesc puncte de frontierã.
Orice mulþime poliedralã se poate descompune în tetraedre. Demonstraþia rezultã din proprietãþile de descompunere a prismelor, piramidelor ºi trunchiurilor de piramidã. Proprietate 1. Orice prismã se descompune în prisme triunghiulare. Demonstraþie : Se considerã prisma P cu bazele S ºi S' . ªtim cã suprafaþa poligonalã S se descompune în suprafeþe triunghiulare µ §. Prismele determinate de bazele µ §, planul bazei S' ºi având muchiile laterale paralele cu muchiile laterale ale prismei P au interioare disjuncte ºi reuniunea lor coincide cu P. (fig.1a) Proprietate 2. Orice prismã triunghiularã se descompune în trei tetraedre. Demonstraþie : Se considerã prisma µ § ºi piramidele µ §, µ § ºi µ §, aceste trei piramide au interioare disjuncte, deoarece oricare douã dintre ele au ca intersecþie o faþã sau o muchie, iar reuniunea lor este P, deci P se descompune în µ §. (fig.1b) Proprietate 3. Orice piramidã se descompune în piramide triunghiulare. Proprietatea rezultã din faptul cã baza piramidei se descompune în suprafeþe triunghiulare care împreunã cu vârful piramidei determinã piramide ce realizeazã descompunerea. (fig.1c) Proprietate 4. Orice trunchi de piramidã se descompune în trunchiuri de piramidã triunghiulare. Proprietatea este consecinþã a proprietãþii 3, fig.2a. Proprietate 5. Orice trunchi de piramidã triunghiularã se descompune în trei tetraedre. Descompunerea este analoagã celei din proprietatea 3, fig.2b. Dacã douã mulþimi poliedrale sunt congruente ºi una din ele este descompusã în tetraedrele µ § atunci ºi cealaltã poate fi descompusã în tetraedrele µ § astfe ca µ §, i = 1,2,¡Kn. Un corespondent în spaþiu al suprafeþelor poligonale cu frontiera poligon îl constituie poliedrele. O mulþime poliedralã P se numeºte poliedru dacã are urmãtoarele proprietãþi : Pentru orice douã puncte interioare ale lui P, existã o linie poligonalã cu extremitãþile în cele douã puncte, formatã numai din puncte interioare. Pentru orice douã puncte care nu aparþin lui P existã o linie poligonalã cu extremitãþile în cele douã puncte, formatã numai din puncte care nu aparþin lui P. Se numeºte vârf al unui poliedru un punct care aparþine frontierei poliedrului ºi nu aparþine nici unui segment deschis inclus în frontierã. Se numeºte muchie a unui poliedru un segment determinat de douã vârfuri ale poliedrului, inclus în frontierã ºi ale cãrei puncte nu aparþin interiorului nici unei suprafeþe poligonale inclusã în frontierã. Un poliedru se zice convex dacã este mulþime convexã. În cazul unui poliedru convex, frontiera este o reuniune de suprafeþe poligonale convexe, a cãror laturi sunt muchii ale poliedrului. O astfel de suprafaþã poligonalã convexã se numeºte faþã a poliedrului. Se numeºte reþea poligonalã simplã o suprafaþã poligonalã [P] cu frontiera poligon, împreunã cu o descompunere a ei în suprafeþe poligonale convexe µ §. Cele f suprafeþe [Pi] se numesc feþele reþelei, iar vârfurile ºi laturile acestora se numesc vârfurile ºi muchiile reþelei, numãrul lor fiind notat cu v respectiv m.
În orice reþea poligonalã simplã avem µ §. Demonstraþie : Dacã Pi are 4 laturi sau mai multe, ducând o diagonalã a lui Pi, se obþine o reþea nouã în care numãrul vârfurilor este tot v, dar existã o muchie în plus ºi o faþã în plus, deci numãrul µ § nu s-a modificat. Aºadar, dacã descompunem fiecare [Pi] în suprafeþe triunghiulare, se obþine o reþea pentru care µ § rãmâne acelaºi. Deci este suficient sã demonstrãm teorema pentru cazul când fiecare Pi este triunghi. Aplicãm inducþia matematicã în raport cu f. Dacã f = 1 avem un singur triunghi, deci v = 3, m = 3 ºi deci µ §. Presupunem proprietatea adevãratã pentru orice reþea în care numãrul feþelor este mai mic sau egal cu f-1. Considerãm o suprafaþã triunghiularã [ABC] a reþelei având latura [AB] în comun cu P ºi deosebim douã cazuri: C este un punct interior lui [P] (fig.3). Scoþând din reþea µ §, se obþine o reþea simplã cu f-1 feþe, v vârfuri ºi m-1 muchii. În virtutea ipotezei din inducþie avem : µ §. Deci µ §. Dacã µ §, (fig.4), atunci [AC] sau [BC] descompune reþeaua [P] în reþele poligonale simple [P'] ºi [P''] cu v', m', f' respectiv v'', m'' ºi f'' vârfuri, muchii ºi feþe pentru care µ § ºi µ §. Deoarece µ §, µ § ºi µ § µ § ºi deci µ §. Teorema 3. Dacã v, m, f reprezintã respectiv numãrul vârfurilor, muchiilor ºi feþelor unui poliedru convex, atunci µ §.
Fie µ § o faþã a lui P, µ § planul lui L, iar µ § un plan paralel cu µ §, astfel ca poliedrul P sã fie situat între µ § ºi µ §. Luãm un punct µ § ºi o dreaptã µ §, N ºi IntP fiind de o parte ºi de alta a lui µ §. Notãm cu µ §, µ §, µ § este un poligon convex asemenea cu µ § ºi dacã N este suficient de aproape de M, punctele µ § se aflã în interiorul lui µ §. Prin urmare punctele µ § sunt vârfurile unei reþele poligonale simple având v vârfuri, m muchii ºi f feþe.din teorema 2 µ § deci µ §. Observaþie : Dacã se suprimã faþa L se obþine o reþea spaþialã simplã R, aºezatã pe suprafaþa poliedrului P. Acesteia i-am asociat prin „proiectarea din N ” o reþea poligonalã simplã în planul µ §. Bazându-ne pe intuiþie, putem sã obþinem asocierea respectivã ºi în alt mod. Ne imaginãm cã reþeaua R este realizatã dintr-o membranã elasticã pe care o întindem pânã ce devine planã, ea se deformeazã ºi muchiile devin arce de curbe, dar acestea pot fi înlocuite cu segmente de drepte fãrã a schimba numãrul v, m ºi f-1 ºi teorema 3 rezultã din teorema 2. Acest procedeu poate fi aplicat ori de câte ori reþeaua spaþialã, presupusã elasticã, poate fi întinsã astfel încât sã devinã planã. Deci relaþia lui Euler este valabilã ºi pentru alte tipuri de poliedre, nu numai pentru cele convexe. (fig.5) Fie corpul din figura 6 pentru care v = 9, m = 16, f = 9 ºi µ § µ §µ § acest corp poate fi întins în plan. Dacã considerãm corpul din figura 7, de formã inelarã, reþeaua feþelor rãmase nu se mai poate întinde pe un plan ºi avem: v = 16, m = 32, f = 16 ºi µ §. Dacã un corp este strãpuns de p ori, zicem cã suprafaþa lui este de „gen p” ºi în acest caz µ §. Numãrul µ § se numeºte caracteristica eulerianã a suprafeþei respective. Suprafaþa unui poliedru convex este de „gen O” ºi are carqacteristica eulerianã egalã cu 2. Un poliedru convex P se numeºte poliedru regulat dacã fiecare vârf a lui P aparþine aceluiaºi numãr de muchii, toate feþele sunt suprafeþe poligonale regulate congruente ºi toate unghiurile diedre, determinat de feþe cu muchie comunã sunt congruente. Teoremã 4 Existã numai cinci tipuri de poliedre regulate ºi anume: tetraedrul, hexaedrul (cubul) octoedrul, dodecaedrul ºi icosoedrul regulat. Demonstraþie: Notãm prin q numãrul muchiilor de pe o faþã ºi cu p numãrul muchiilor care pleacã dintr-un vârf. Pentru cã fiecare muchie e inclusã în douã feþe ºi are douã vârfuri, rezultã: µ §, deci (1) µ § ºi µ § Dar din relaþia lui Euler avem µ § sau (2) µ § Deci (3) µ § de unde µ §. Deci µ §, la fel ºi µ §, iar dacã µ § atunci µ §. Aºadar singurele perechi µ § care verificã inegalitatea (3) sunt: (4) (3,3), (3,4), (3,5), (4,3), (5,3) Deci existã cel mult cinci tipuri de poliedre regulate. Arãtãm cã pentru fiecare pereche din ºirul 4 existã un poliedru regulat. Dacã p = 3 ºi q = 3 Din (2) obþinem m = 6, iar din (1) obþinem v = 4 ºi f = 4, acesta este tetraedrul regulat. Dacã p = 3 ºi q = 4 µ § ºi µ §, acesta este cubul sau hexaedrul regulat (figura 8a). Cazul µ § ºi f = 8, acest poliedru poate fi realizat luând ca vârfuri centrele feþelor unul cub (figura 8a). Cazul µ § ºi f = 20, acest poliedru poate fi realizat în felul urmãtor: Se considerã într-un plan µ § un pentagon regulat ABCDE, de centru O ºi laturã a. Pe dreapta dusã prin O, perpendicularã pe µ § se ia un punct F astfel ca AF = a. Atunci triunghiurile FAB, FBC, FCD, FDE ºi FEA sunt echilaterale. Se ia un punct O’ pe semidreapta opusã lui /OF, se duce planul µ § prin O’, paralel cu µ § ºi se proiecteazã punctele A,B pe µ § în A'B'. Înscriem în cercul C(O',OA) situat în µ § un pentagon regulat GHIJK astfel încât G sã fie mijlocul arcului mic A'B'. Determinãm distanþa µ § aºa încât µ §, notãm în acest scop cu M mijlocul segmentului (AB) ºi cu N mijlocul arcului mic AB al cercului circumscris lui ABCDE; rezultã µ §. Între planele µ § ºi µ § se formeazã zece triunghiuri echilaterale: ABG, BCH, DEJ, EAK, GHB, HIC, IJP, JKE, KGA. Pe semidreapta opusã lui O'F luãm punctul L pentru care O'L=OF se obþin alte cinci triunghiuri echilaterale de laturã a: GHL, HIL, IJL, JKL, KGL ºi [FABCDEGHIJKL] este un poliedru regulat cu 20 de feþe, numit icosaedru regulat (figura 8b ºi 8c). Cazul µ § Centrele feþelor unui icosaedru regulat formeazã vârfurile unui poliedru regulat cu 12 feþe numit dodecaedru regulat (figura 8d). fig.8a fig.8b
fig.8c fig.8d
Problema 1 Un vârf al unui patrulater ABCD se marcheazã dacã ºi numai dacã el este situat în interiorul unghiului opus. Sã se demonstreze: Cel puþin unul din vârfurile A, B, C, D va fi marcat; Dacã douã vârfuri sunt marcate, atunci patrulaterul este convex ºi toate vârfurile vor fi marcate. Demonstraþie: Fie ABCD un patrulater, el poate fi convex sau neconvex. Dacã ABCD este patrulater convex µ §, din faptul cã diagonalele unui patrulater convex au un punct comun, cã toate vârfurile sale sunt situate în interiorul unghiului opus ºi deci toate vârfurile sunt marcate. Dacã ABCD este patrulater neconvex, existã cel puþin o laturã, sã zicem [AB], al cãrui suport separã celelalte vârfuri C ºi D, deci µ § ºi µ §. Evident cã µ § deoarece definiþia poligonului nu admite poligoane care se autointersecteazã. Din µ §µ § ºi µ § sau µ §. Cazul I. µ § Vom arãta cã µ §, µ § ºi µ § adicã B este un vârf marcat, iar A, C, D sunt nemarcate. Notãm AB = a, BC = b, DA = d, µ § ºi avem µ § ºi µ §, dar µ § ºi µ § din µ § ºi µ §, dar µ §, dar µ § ºi µ §, din µ §, dar µ § ºi deci µ § ºi µ §= =µ §. Arãtãm cã µ §, µ § ºi µ §. 1) µ §µ §µ § 2) µ §µ § din µ §, dar µ § µ §. µ §µ §, µ §µ § Cazul II. µ § - se trateazã analog Dacã douã vârfuri ale unui patrulater sunt marcate, atunci patrulaterul este convex, un patrulater neconvex are un singur vârf nemarcat, deci toate vârfurile sunt marcate. Problema 2. Intersecþia semiplanelor închise limitate de suporturile laturilor unui poligon convex P coincide cu mulþimea µ §. Demonstraþie: Fie poligonul µ § Fie I intersecþia consideratã. Se ºtie cã µ § este intersecþia semiplanelor deschise limitate de suporturile laturilor poligonului ºi care conþine vârfurile nesituate pe laturile respective. Dar orice semiplan deschis este inclus în semiplanul închis mãrginit de aceeaºi dreaptã, deci intersecþia semiplanelor închise µ §. Din convexitatea poligonului P rezultã cã pentru fiecare laturã µ §, toate vârfurile diferite de PK ºi PK+1 se gãsesc de aceeaºi parte a dreptei PKPK+1. Deci existã în I un singur semiplan închis mãrginit de PKPK+1 care include frontiera sa. Dar µ § µ §, deci µ § ºi µ § µ §. Demonstrãm incluziunea inversã, adicã µ §. Fie µ §, deci µ § tuturor semiplanelor închise nemãrginite de suporturi laturile µ §. Pentru M avem urmãtoarele situaþii: 1) µ § µ § dar M aparþine tuturor semiplanelor închise mãrginite de dreapta µ §, deci M aparþine intersecþiei lor, µ § deci µ §. 2) Existã K, aºa încât µ §, dar M se gãseºte ºi în toate celelalte n-1 semiplane închise mãrginite de suporturile celorlalte laturi diferite de µ §. Deci M se gãseºte ºi în semiplanul închis mãrginit de dreptele µ § ºi care conþine ºi celelalte vârfuri diferite de Pk-1 ºi Pk, rezultã deci cã M ºi Pk+1 sunt de aceeaºi parte a dreptei µ § ºi deci µ §. La fel se gãseºte ºi în semiplanul mãrginit de dreapta µ § ºi care conþine celelalte vârfuri M ºi Pk sunt de aceeaºi parte a dreptei µ § deci µ §. Yüklə 175,66 Kb. Dostları ilə paylaş:
|