Grafic F (V, E) pot fi reprezentate geometric. În acest scop, un spațiu n-dimensional al punctelor marcate elemente ale setului V de vârfuri și vi vârfuri și vj sunt conectate linie dacă vi. vj>Î E. Imaginea geometrică a graficului va fi numit o diagramă.
Exemplul 3.1. Să V = v1, v2, v3, v4>, și E sunt elementele de toate seturile posibile de forma vi. vj> cu i, j = 1,2,3,4; i¹j. grafic diagrama prezentată în Fig. 3.1, de asemenea.
Să presupunem acum că mulțimea E = E1, E2. em> reprezintă o relație binară pe setul V (E ÍV'V). Apoi, perechea de seturi V și E se numește un grafic direcționat (digraph) F (V, E) cu V un set de noduri și set E de margini.
Edge a unui grafic direcționat este numit un arc. Pentru arc ek = (vi. Vj) se spune că vi inițial vertex. și vj - .Inymi cuvinte finale, margine ek merge de la vi vertex și intră în partea de sus a VJ. Ca și în cazul rib neorientat, vI vârfuri arc ekintsidentna și vj. și nodurile vi și ek arc vjintsidentny. Vertex vi si vj este, de asemenea, numit adiacente.
Nervura, care punctele finale sunt aceleași, se numește buclă.
Exemplul 3.2. Fie V =. Definim pe raportul set
grafic diagrama prezentată în Fig. 3.1 b.
Din definițiile de mai sus ale graficelor arată că le lipsește multipli. sau paralel. margini care leagă aceeași pereche de noduri. În plus, bucla nu este permisă într-un grafic neorientat. Cu toate acestea, uneori este convenabil pentru a elimina aceste limitări.
Count cuprinzând mai multe muchii se numește multigraf. Count cuprinzând bucle și (sau) muchii multiple, numite pseudographs.
Două grafice F și F * sunt izomorfe. în cazul în care există o corespondență unu la unu între seturile de noduri V și V *, care nodurile sunt conectate cu marginile într-un grafic și apoi numai când nodurile lor corespunzătoare sunt conectate într-o altă coloană. În cazul în care sunt orientate coaste, direcția lor trebuie să corespundă, de asemenea, unul de altul. Toate graficele izomorfe au aceleași proprietăți.
Vertex nu incident de la orice margine se numește izolat. Graf, sostoyaschiytolkoiz vârfuri izolate, se numește un grafic nul (graficul gol) și este notat cu 0. Pentru zero set de muchii ale grafului - goale: E =Æ.
Un alt caz special important este un grafic complet. în care fiecare set vertex V este conectat la toate celelalte noduri de margine ale setului. Sensibilul Graficul neorientat complet cu n noduri vor fi notate cu Kn .żn grafic complet orientat are două margini pentru fiecare pereche de vârfuri: unul în fiecare direcție.
Exemplu. Fig. 3.1, și a prezentat grafic K4.
Un tip deosebit de important al pieselor cuprind subgrafurilor. Fie V * să fie Í V. subgrafic F * (V * E *) Earl F - aceasta este o parte a graficului F (V. E), mulțimea muchiilor E *, care constă din toate muchiile grafului F (V. E), ambele capete ale care se află în V *.
Dacă V * = V. subgrafic F * (V *, E *) coincide cu F (V. E). Altfel subgrafic F * (V * E *) se numește subgraf corespunzătoare F * (V * E *). Pentru un singur nod V * = a> subgrafic F * (V * E *) este format din bucle într-un.
Exemplu (fig. 3.3). Pentru un grafic 3.3 și graficul 3.3, B este o parte, dar nu este un subgraf, atunci graful este 3.3, 3.3 este contele, ci ca parte subgrafic.
Numărul graficelor neorientate cu n noduri
Să presupunem că există n noduri etichetate în mod corespunzător: v1. v2. vzg. Noi contoriza numărul de diferite diagrame care pot fi construite pe aceste noduri. Numărul maxim de muchii din graficul determinat de numărul de moduri de n noduri pot selecta două: a = Cn 2. Există două posibilități pentru fiecare muchie: fie este realizată sau nu. În conformitate cu regula funcționează în combinatorica, numărul de diagrame și, prin urmare, graficul este 2a.
Numărul graficelor neorientate cu n noduri și m muchii
Ca și înainte, să nu fie n vârfuri etichetate în mod corespunzător: V1. v2. vzg. Graficele cu m margini la fel de mult ca și există modalități de toate o = Cn 2 coaste alege m margini, și anume ca m.