graf neorientat cu șase vârfuri și șapte muchii
În matematică teoria grafurilor și calculator grafic - o colecție de obiecte cu legături între ele.
Obiectele sunt reprezentate ca noduri. sau grafic noduri si link-uri - cum ar fi arc. sau coaste. Pentru diferite aplicații, diferite tipuri de grafice pot fi orientate, restricții cu privire la numărul de link-uri și date suplimentare cu privire la noduri sau muchii.
defini
Sau graf neorientat grafG - o pereche ordonată G. = (V, E). pentru care sunt îndeplinite următoarele condiții:
- V este multimea de noduri sau noduri,
- E este multimea de perechi (în cazul unui graf neorientat - dezordonate) vârfuri diferite, numite muchii.
V (și, prin urmare, E) sunt în general considerate seturi finite. Multe rezultate bune pentru graficele finite, incorecte (sau în orice alt mod) pentru grafice infinite. Acest lucru se datorează faptului că o serie de considerații devin false în cazul seturilor infinite.
Nodurile și marginile graficului sunt, de asemenea, numite elemente ale graficului, numărul de noduri într-un grafic | V | - comandă. numărul de muchii | E | - dimensiunea graficului.
Nodurile u și v sunt numite noduri terminale (sau se termină) margini e = u, v>. Edge, la rândul său, se conectează partea de sus. Două vârfuri de capăt ale aceleiași coaste sunt numite vecini.
Două margini sunt numite adiacente. în cazul în care acestea au un nod final comun.
Două margini sunt numite multipli. în cazul în care o multitudine de noduri de capăt coincid.
O margine se numește buclă. Dacă capetele sunt aceleași, adică, e = v, v>.
DegV grade vertex V numit numărul de muchii pentru care este un scop (bucla este considerată de două ori).
Vertex este numit izolat. în cazul în care acesta nu este sfârșitul pentru orice fin; agățat (sau foaie), în cazul în care acesta este sfârșitul exact o muchie.
grafic regia
Un grafic direcționat (digraph scurt) G - este o pereche ordonată G. = (V, A). pentru care sunt îndeplinite următoarele condiții:
- V este multimea de noduri sau noduri,
- A este multimea (ordonate) de diferite perechi de noduri numite arce sau muchii orientate.
Arc - o pereche ordonată de noduri (v, w). unde vertex v este numit la început și w - end arc. Se poate spune că arcul w v conduce la vertex v trece prin punctul w.
Număr mixt
grafG mixt - un grafic în care pot fi orientate unele margini, iar unele - neorientate. Înregistrate ordonate triplu G. = (V, E, A). unde V. E și A sunt definiți la fel ca mai sus.
Este clar că graficele orientate și neorientate sunt cazuri speciale de amestec.
Alte definiții corespunzătoare
Path (sau lanț) în grafic este o secvență finită de noduri, în care fiecare nod (cu excepția ultimului) este conectat la alta în secvența de noduri ale marginii.
Orientată de o digraph este o secvență finită de vârfuri vi, care pentru toate perechile (vi, vi + 1) sunt (orientate) margini.
Un ciclu este o cale în care primul și ultimul nodurile sunt aceleași. Când această lungime cale (sau ciclul) este numărul de marginile sale constitutive. Rețineți că, dacă nodurile u și v sunt capetele unei margini, apoi conform definiției, o secvență (u, v, u) este un ciclu. Pentru a evita astfel de cazuri „degenerate“, introduc următoarele concepte.
Calea (sau ciclu), se numește simplu. în cazul în care marginile nu se repetă; elementar. în cazul în care acesta este un simplu și vârfuri în ea nu se repetă. Este ușor de observat că:
- Fiecare mod de a conecta cele două vârfuri conține o cale elementară care leagă aceleași două vârfuri.
- Fiecare cale simplă conține ciclu elementar non-elementar.
- Fiecare ciclu simplu, trece printr-un nod (sau margine) cuprinde elementar buclă (sub-) care se extinde prin același vertex (sau margine).
O relație binară pe mulțimea de noduri specificate ca „există o cale de la u la v», este o relație de echivalență. și, prin urmare, rupe setul de clase de echivalență, numite componente ale graficului. În cazul în care numărul este exact un component conectat, graficul este conectat. In componenta conectată poate introduce conceptul de distanță între vârfurile ca o cale de lungime minimă conectarea acestor noduri.
Fiecare subgraf maximal conectat de un grafic G este o componentă conectată (sau componentă) a graficului G. Termenul „maxim“ înseamnă includerea unui maxim, care nu este conținută într-un subgraf conectat cu un număr mare de elemente
Edge a graficului este numit un pod. în cazul în care eliminarea acestuia crește numărul de componente.
Caracteristici suplimentare a graficului
- conectat. dacă pentru oricare două noduri u. v există o cale de la u la v.
- orientat puternic conectat sau conectat. în cazul în care este orientat, și de la orice nod la orice alt există o cale îndreptată.
- copac. în cazul în care este conectat și nu conține cicluri simple.
- completă. dacă oricare dintre cele două (ridicat în cazul în care bucla nu este permis), nodurile conectate de margine.
- bipartite. în cazul în care nodurile sale pot fi împărțit în două subseturi disjuncte V1 și V2, astfel încât fiecare margine se conectează un vârf al unui V1 V2 de la vârf.
- k-Dolny. în cazul în care nodurile sale pot fi împărțite în k disjuncte subseturi V1. V2. ..., Vk, astfel încât vor exista margini de conectare vârfuri ale aceluiași subset.
- bipartit complet. în cazul în care fiecare nod dintr-un subset este conectat la o margine la celălalt subset nod.
- planare. în cazul în care graficul poate fi reprezentat de diagrama pe planul fără a trece margini.
- ponderat. În cazul în care fiecare muchie este atribuit un anumit număr numit greutatea marginii.
Moduri de a reprezenta un grafic în informatică
Matricea adiacență
Matricea de adiacență - un tabel, unde coloanele și rândurile corespund nodurile graficului. În fiecare celulă a numărului matricei este înregistrată, indicând dacă comunicarea din rândul de sus la partea superioară a coloanei (sau invers).
Dezavantajul este cerințele de memorie - în mod evident, numărul de noduri ale pătrat.
matrice de incidență
Fiecare linie corespunde unui nod specific al graficului, iar coloanele corespund graficului relațiilor. Celula în linie i-lea cu coloana j-a matricei este scris:
1, în cazul în care conexiunea j «afară» din punctul I. -1 în cazul în care conexiunea „vine“ în partea de sus, orice număr diferit de 0, 1, -1, în cazul în care conexiunea este o buclă, 0 în toate celelalte cazuri.
Această metodă este cea mai încăpător (dimensiune este proporțională cu | E | | V |) și incomod pentru depozitare, dar este mai ușor să găsească cicluri în grafic.
Listă de coaste
Listă de margini - este un tip de reprezentare grafic în memorie, ceea ce înseamnă că fiecare muchie este reprezentată de două numere - numerele vârfurile coaste. Listă de coaste este mai convenabil să pună în aplicare diferite algoritmi pe grafice, în comparație cu matricea de adiacenta.
Generalizarea conceptului a graficului
Mai abstract, graficul poate fi setat ca trei, unde V și E - Unele seturi (vârfuri și muchii, respectiv, ..), și - o funcție de incidență (sau incidentor), care atribuie fiecare margine (ordonate sau neordonate) pereche de vârfuri u și v din V ( se termină). Cazuri particulare ale acestui concept sunt:
- grafice direcționate (digraphs) - când vreodată este o pereche ordonată de noduri;
- grafice neorientate - așa cum este întotdeauna pereche dezordonată de vârfuri;
- grafice mixte - în care există ambele margini și bucle dirijate și nedirijate;
- Euler grafice - grafic în care există un traseu circular (ciclu Euler) Euler.
- multigraphs - grafice cu mai multe margini, care au capetele lor aceeași pereche de noduri;
- pseudographs - l multigraphs recunoaște existența bucle;
- grafice simple - fără bucle și margini multiple.
Definiția nu se potrivește unele dintre celelalte generalizările prezentate mai sus:
literatură
Programe populare pentru desen grafic
Vezi ce „digraph“ în alte dicționare:
digraph - orientuotasis grafas statusas T sritis AUTOMATIKA atitikmenys: angl. grafic direcționat; orientate grafic vok. gerichteter Graph, m; Grafic orientierter, m rus. digraph, m; grafic îndreptat, m pranc. graphe de fluență, m; graphe Directe, m; graphe ... ... Automatikos terminų žodynas
componentă conectată ferm - numit digraph puternic conectat (. engleză puternic conectat), În cazul în care oricare două dintre nodurile sale sunt puternic conectate. Două vârfuri s și t orice grafic este conectat puternic în cazul în care există o cale direcționată de la s la t, și o cale îndreptată de la T s. ... ... Wikipedia
componentă a graficului conectat ferm - este numit un digraph puternic conectat (puternic conectat), în cazul în care oricare două dintre nodurile sale sunt puternic conectate. Două perechi de vârfuri s și t fiecare conectat puternic grafic, dacă există o cale îndreptată de la s la t, și o cale direcționată de la t la s. conectat ferm ... ... Wikipedia
Regizat grafic - (pe scurt digraph) (mai multe) grafic ale cărui margini atribuite direcția. marginile sunt dirijate, de asemenea, numite arcuri, iar unele surse (Ore) și doar marginile ... Wikipedia
Teoria grafurilor - în chimie, zona finală a matematicii care studiază structurile discrete se numește. grafice; Acesta este utilizat pentru o varietate de teoretic. și aplicații. Unele concepte de bază. Contorizarea setul de puncte (noduri) și o multitudine de perechi de puncte (... ... Chemical Encyclopedia
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
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