Fig. 1. Count, peste care a marcat grade.
Gradul de vertex (.. grad Engl valența Engl valența ..) în teoria grafurilor - numărul de grafic muchii incidente la vârful. La calcularea gradului de margine buclă numărate de două ori. [1] Gradul de vertex este denumit (în sursele occidentale -). grad maxim și minim de noduri ale graficului G notate cu Δ (G) și δ (G). Fig. 1, gradul maxim este de 5, minim - 0. În gradele de coloană regulate de toate nodurile sunt aceleași, astfel încât în acest caz putem vorbi despre gradul de grafic.
handshaking Lema
Conform formulei pentru suma gradelor graficului,
adică suma gradelor de vârfurile unui grafic este egal cu dublul numărului de marginile sale. În plus, formula afirmă că orice număr de vârfuri ale graficului de grad impar chiar. Această afirmație (și formula în sine) sunt cunoscute ca lemma handshaking. Numele vine de la problema matematică bine-cunoscut: este necesar să se demonstreze că, în orice grup de numărul de persoane care să dea mâna cu un număr impar de alte chiar.
Secvența de grade vertex
Fig. 2. Două grafic izomorf cu grade egale de secvență (3, 2, 2, 2, 2, 1, 1, 1).
Secvența de grade vertex neorientat grafic este o secvență non-creștere. [2] Pentru graficul prezentat în Fig. 1, este (5, 3, 3, 2, 2, 1, 0). Secvența de grade vertex graficului există un invariant. deci este același grafice izomorfe. Cu toate acestea, secvența de grade vertex nu este unic Count Specificații de mediu: în unele cazuri, grafice non-izomorfe au, de asemenea, aceeași secvență.
Problema grade secvențe este de a găsi unele sau toate numărătorilor cu secvența non predeterminată în creștere care constă din numere naturale (zero grade, astfel, pot fi ignorate, deoarece valoarea lor este modificată prin adăugarea sau eliminarea vârfuri izolate). Secvența este o secvență de grade a unui grafic se numește (Eng. Secvență grafică) grafică. Formula suma puterilor rezultă că orice secvență cu suma impar (ca, de exemplu, 3, 3, 1) nu poate fi grade graficul de secvență. Reciproca este, de asemenea, adevărat: în cazul în care secvența a chotnuyu cantitate, este o secvență de grade multigraf. Construirea un astfel de grafic se realizează într-un mod simplu: este necesar să se combine vârful puteri impare în perechi. la vârfurile necompletate rămase trebuie adăugate la bucla.
Este mai dificil să pună în aplicare un grafic simplu, cu o secvență predeterminată. Teorema Erdos - Gallai susține că o creștere a secvenței di (dacă i = 1, ..., n) poate fi o secvență de grafic simplu numai dacă valoarea sa chiar și inegalitate
De exemplu, secvența (3, 3, 3, 1) nu poate fi o secvență de grafic simplu; satisface Erdos - Gallai numai când k este 1, 2 sau 4, dar când k nu este egal cu 3.
S. L. Hakimi a demonstrat că (d1, d2, ..., dn) este o secvență de grade de grafice simple, numai dacă există (d2 - 1, d3 - 1, ..., DD1 +1 - 1, DD1 +2 DD1 +3 .. ..., dn). Acest fapt a permis de a dezvolta un algoritm simplu pentru a găsi grafic simplu, cu o secvență predeterminată pusă în aplicare:
- Inițial, graficul nu are margini.
- O listă de noduri la care puterile cerințelor nu este încă îndeplinită. Cerințele rămase sunt aranjate în ordine crescătoare.
- Primul vârf este conectat cu următoarea d1 în fruntea listei. După aceea, primul Vertex este eliminat, re-ordonați lista. Acțiunea se repetă până când, până când sunt îndeplinite toate cererile.
Problema găsirii numărului de grafice sau de evaluare se referă la transferul unei secvențe predeterminate de grafice.
valori particulare
Fig. 3. nodurile terminale sunt 4, 5, 6, 7, 10, 11 și 12.
- Vertex de grad 0 este numit izolat.
- 1 se numește gradul de capătul vertex (Engl. End vertex), spânzurarea (Engl. Pendant vertex) sau foaie grafic (Engl. Leaf vertex). Edge incident de la un nod se numește (Eng. Terminal (pandantiv) margine, final margine) agățat. Fig. 3 este o nervură agățat. O astfel de terminologie este folosită în studiul de arbori, în general, și ca structuri de date.
- Partea superioară a gradului n-1 al graficului se numește ordine dominant n (Engl. Vertex Dominând).
proprietăți comune
- În cazul în care toate nodurile au același grad k. Un grafic se numește k-regulat sau grafic regulat al grad k. În acest caz, contele însuși are un k.
- calea Eulerian există într-un graf neorientat, conectat dacă și numai dacă graficul este 0 sau 2 noduri grad impar. În cazul în care un grafic conține un vârf de 0 grade ciudat, calea Eulerian este un ciclu.
- Digraph este psevdolesom numai dacă indegree fiecare nod nu este mai mare decât 1. Graficul funcțional - psevdolesa cazul special în care abordarea jumătate de grad de toate nodurile sunt egale cu 1.
- Conform Teorema Brooks numărul cromatic al unui grafic sau clică, cu excepția ciclului ciudat nu depășește limita maximă a nodurilor sale (A). Conform Teorema Vizinga, indicele cromatic al unui grafic nu este mai mare de Δ + 1.
- k grafic degenerării este un grafic în care fiecare subgrafic are noduri de grad nu este mare k.
- Indegree și vertex outdegree regia grafice
- distribuție de studii
notițe
Vezi ce „grad topuri (teoria grafurilor)“ în alte dicționare:
Doug (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 T U V ... Wikipedia
Ciclul (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 T U V ... Wikipedia
Arbore (teoria grafurilor) - În acest termen, există alte utilizări, vezi arborele (dezambiguizare) .. Un arbore este un grafic aciclic conectat. [1] Conectivitatea înseamnă a avea căi între orice pereche de vârfuri aciclicitate nici un cicluri și că, între perechile de noduri ... ... Wikipedia
Teoria grafurilor - secțiunea finală de matematică (. A se vedea Ultimate Math), O caracteristică care este abordarea geometrică a studiului obiectelor. Conceptul de bază al teoriei graficului. Earl este dat un set de noduri (puncte) și setul de muchii (link-uri), care se conectează ... Marii Enciclopedii Sovietice
Glosar de teoria grafurilor - Această pagină glosar. . A se vedea, de asemenea, articolul principal: Teoria grafurilor Aici sunt colectate definițiile teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină) ... 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
Aplicarea practică a graficului de colorat - Acest articol ar trebui să fie vikifitsirovat. Vă rugăm să-l facă în conformitate cu regulile de baza documentelor de înregistrare. Graficul de colorat este folosit practic (setarea problema razlichinyh de colorat nu vor fi discutate aici) pentru ... Wikipedia
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
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
- Gradul de vârf (teoria grafurilor). Dzhessi Rassel. Această carte va fi făcută în conformitate cu comanda pe tehnologia de imprimare Tehnologie-on-Demand. Conținutul de calitate înaltă prin articole wikipedia! vertex grade (. grad Eng, valența engleză. ... Citește mai mult Cumpără pentru 1.125 de ruble