Planar grafic - l

Contele Planar - conta, care poate fi reprezentată pe un plan, fără a trece coaste.

Mai strict: Graf este plasat pe o suprafață, în cazul în care se poate desena pe ea, fără a trece margini. Laid un grafic se numește geometrică. Summit-ul său este un punct în plan, iar linia de creasta pe ea, câmpul la care contele sparge fețele de suprafață numite. Plat Earl - Earl a pus pe un plan. Un grafic se numește plan. în cazul în care este izomorf cu un grafic plan.

Criteriul non-planeitate

K5. grafic complet cu 5 noduri

K3,3. grafic ce ilustrează problema din cele trei sonde

• condiție suficientă - dacă graficul are un K3,3 subgraf bipartit sau subgraf complet K5. nu este plană;
• condiție necesară - dacă graficul nu este plană, atunci ar trebui să conțină mai mult de patru noduri de grad mai mare de 3 sau mai mare de 5 noduri de grad mai mare de 2.

Teorema de Pontryagin-Kuratowski

Grafic este plană, dacă și numai dacă nu conține subgrafurilor contractate la K5 sau K3,3.

Formula lui Euler

Pentru un grafic planar conectat următoarea relație dintre numărul de vârfuri V, margini și fețe E F:

Euler în 1736 sa constatat [1] în studiul proprietăților poliedre convexe. Această relație este valabil și pentru alte suprafețe de până la un coeficient, numit caracteristica Euler. Această suprafață invariant, un plan sau sferă este egal cu doi.

Formula are multe efecte utile. Din faptul că fiecare fațetă este delimitată de cel mult trei coaste, că pentru un grafic planar

adică, cu un număr mai mare de muchii ale nonplanar cunoscute. (Reciproca nu este adevărat exemplu.) Rezultă că într-un grafic planar poate găsi întotdeauna un vârf de grad cel mult 5.

grafice planare în probleme

Problema celor trei sonde. Există trei case și trei puțuri. Aceasta dovedește că este imposibil ca să deschidă calea între case și fântâni, pentru fiecare casă la fiecare pistă bine păstrate, și nu există două căi nu ar trece. (Poduri nu poate fi construit.)

carduri de colorat. Este necesar să picteze un număr plat de pe hartă de culori, astfel încât oricare două țări care au o porțiune comună de frontieră au culori diferite. Se pare că, în absența enclave. întotdeauna suficiente patru culori, dar această afirmație este extrem de dificil de a dovedi, a se vedea. Teorema patru culori.

notițe

Vezi ce un „grafic planar“ în alte dicționare:

GRAFICUL EXTREME - grafic pe rom una sau alta caracteristica numerică ia minimă sau valoarea maximă. De obicei, se găsesc valori extreme ale unei anumite caracteristici numerice ale unui roi și restricții cu privire la alte caracteristici numerice si ... ... Enciclopedia Matematica

GRAFICUL PLAT - grafic planar, graficul capabil sa pliat corect în planul (a se vedea de stivuire coloană.). Cu alte cuvinte, graful G se numește. plat, în cazul în care acesta poate fi reprezentat pe un plan, astfel încât nodurile corespund diferitelor puncte ale planului, iar liniile ... ... Enciclopedia de Matematică

GRAFICUL - multe Vvershin și a stabilit Eneuporyadochennyh și a ordonat perechi de noduri; G. desemnat prin. pereche neordonată de vârfuri se numește. coaste, o pereche ordonată de arc. G. conține numai margini, numite. nedirijate; G. conține numai arc ... ... Enciclopedia de Matematică

Graf bipartit - graficul bicromatic, al cărui set de noduri la cerned pot fi împărțite în două subseturi disjuncte, și. (T ... Enciclopedia de Matematică

Vertex (grafic) - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S T U V ... Wikipedia

Planar grafic - grafic grafic planar, care poate fi reprezentată pe un plan, fără a trece coaste. Mai strict: Graf este plasat pe o suprafață, în cazul în care se poate desena pe ea, fără a trece margini. Laid un grafic se numește geometric ... Wikipedia

Grafic Laman - In teoria grafurilor graficul Lamanova cu n noduri numesc acest grafic G, care, în primul rând, pentru fiecare k fiecare subgraf al lui G, conținând k noduri, nu are mai mult de 2k -3 coaste și, în al doilea rând, graficul G are coaste -3 exact 2n. Lamanova grafice ... Wikipedia

Glosar de teoria grafurilor - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S ... Wikipedia

Lungimea în digraph - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S T U V ... Wikipedia