Tipurile de grafice sunt determinate de principiile generale ale construcției lor, în timp ce cazurile speciale ale graficului depind de diferitele proprietăți de noduri sau muchii.
Un grafic se numește bipartit. în cazul în care setul de noduri sale pot fi împărțit în două subgrupuri, astfel încât nici o muchie nu se unește vârfurile aceluiași subset.
Exemplul 1: Construirea unui grafic bipartit complet.
Grafic complet bipartit compus din două seturi de noduri și a tuturor link-uri posibile, care leagă partea de sus a unui set la un alt set noduri (prezentate mai jos).
Deci, Euler grafic este un grafic în care puteți obține în jurul valorii de toate nodurile și, în același timp, pentru a trece o margine doar o singură dată. În ea, fiecare nod ar trebui să aibă doar un număr par de muchii.
Exemplul 2: Este un grafic complet cu același număr n de margini, care este incident fiecare nod, un grafic Euler? Explicați răspunsul. Dă exemple.
Răspuns. În cazul în care n - număr impar, fiecare nod este incident de n -1 coaste. În acest caz, graficul este un grafic Euler. Exemple de astfel de grafice de mai jos.
Graficul regulată este un grafic conectat, toate nodurile au același grad k. Astfel, de exemplu, în Figura 2 prezintă exemple de grafic regulat, numit gradul nodurilor sale regulate și 4-2-regulate grafice sau grafice regulate de gradul 4 si gradul 2.
Numărul de noduri de grad k regulate nu poate fi mai mică de k + 1. La grafic regulat al ciudat grad poate fi doar un număr par de noduri.
Exemplul 3. grafic Build regulat, în care cel mai scurt ciclu are o lungime de 4.
Decizie. Motivat că, în scopul de a ciclului este îndeplinită lungimea condiției predeterminată, este necesar ca numărul de noduri ale unui multiplu de patru. În cazul în care numărul de noduri este egal cu patru, veți obține un grafic ilustrat în figura de mai jos. El este un obișnuit, dar are lungimea cea mai scurtă ciclul 3.
Creșterea numărului de noduri la opt (următorul multiplu de patru). Noi conectam marginile de sus, astfel încât gradul de Vârfurile au fost egal cu trei. Obținem următorul grafic condiții satisfăcătoare ale problemei.
Grafic Hamiltonian este un grafic care conține un ciclu hamiltonian. Un ciclu hamiltonian este o buclă simplă, care trece prin toate nodurile dintr-un grafic. Astfel, pur și simplu vorbind, graficul hamiltonianul - este un grafic în care puteți obține în jurul valorii de toate nodurile și fiecare nod doar o singură dată, atunci când repetă crawling. EXEMPLU Hamiltonian grafic - de mai jos.
Exemplul 4 un grafic bipartit, unde n - numărul de noduri ale unei multitudini de A. și m - numărul de noduri ale unei multitudini B. In cazul in care graficul este graficul Eulerian, și în acest caz - graficul hamiltonian?
Răspuns. În cazul în care n și n - seara, graficul este Eulerian. Dacă n = n. atunci graficul este hamiltonian.
Grafic Ponderat este un grafic al cărui noduri și (sau) este atribuit coaste „scale“ - de obicei, unele numere. Exemplu de grafic ponderate - rețea de transport, în care marginile sunt atribuite ponderi, ceea ce înseamnă costul transportului mărfurilor de-a lungul marginii și capacitățile arcele. EXEMPLU ponderate graficul de mai jos.
Un arbore este un grafic conectat fără cicluri (vezi figura de mai jos). Orice două noduri sunt conectate printr-un singur traseu copac.
Q Numărul muchiilor grafului este raportul
unde n - numărul de noduri ale arborelui.
Raportul furnizat exprimă valoarea critică a marginilor copacului, ca și dacă adăugăm la copac încă o margine, se va crea bucla, iar dacă uberom o margine, graficul arbore este împărțit în două componente. Graficul constă dintr-o componentă de copac, numit-o pădure.
Sub formă de grafice, în special sub formă de copaci, să construiască o mulțime de modele matematice. care pot fi, de asemenea, găsite pe site-ul nostru.
Intreaga unitate este „Teoria grafurilor“