Digraf (matematică)

În matematică și în special în matematică discretă , prin digraf înțelegem structura relațională de bază , constând dintr-un set finit numit set de noduri și de conexiuni orientate între aceste noduri. Termenii echivalenți sunt graficul direct (digraful este contracția sa) și graficul direcționat .

Descriere

În mod formal, o structură de formă este definită ca un digraf $\,D=\langle Q,U\rangle$ ${\ displaystyle \, D = \ langle Q, U \ rangle}$ ${\ displaystyle \, D = \ langle Q, U \ rangle}$ cu Q mulțime finită numită mulțime de noduri ale lui D și $U\subseteq Q\times Q$ ${\ displaystyle U \ subseteq Q \ times Q}$ ${\ displaystyle U \ subseteq Q \ times Q}$ numit set de arcade de D.

Un grafic orientat poate fi reprezentat grafic desenând fiecare nod cu un cerc și fiecare arc cu o săgeată; un arc „iese” dintr-un nod și „intră” în altul (cel indicat de săgeată). Mai multe arce pot ieși din fiecare nod.

Un digraf este o relație finită însoțită de un set al cărui pătrat cartezian îl conține. Prin urmare, toate distincțiile, toate proprietățile și toate construcțiile introduse pentru relații și care au sens pentru relațiile finite pot fi aplicate digrafelor. Prin urmare, putem distinge digrafele reflexive, antireflective, simetrice, antisimetrice, tranzitive, echivalente, ordonate, gradate, semi-reticulate, reticulate, booleene, funcționale, permutative, involuționare ....

Un digraf poate fi considerat o îmbogățire a unui grafic nedirecționat obținut prin înlocuirea fiecărei margini {p, q} care nu este o buclă cu una sau două margini: {p, q} poate fi înlocuit cu (p, q), cu (q, p) sau cu ambele margini. În consecință, toate distincțiile, proprietățile și construcțiile de pe grafice nedirecționate pot fi adaptate digrafelor, însoțindu-le în general cu distincții adecvate.

La fel ca graficele nedirecționate, digrafele sunt prezentate în mod util prin reprezentări plate.

Un digraf $\,D=\langle Q,U\rangle$ ${\ displaystyle \, D = \ langle Q, U \ rangle}$ ${\ displaystyle \, D = \ langle Q, U \ rangle}$ este identificat prin matricea sa de adiacență , o matrice pătrată binară care corespunde funcției indicator a lui U ca subset de $Q\times Q$ ${\ displaystyle Q \ times Q}$ ${\ displaystyle Q \ times Q}$ . Prin urmare, studiul digrafelor, adică studiul relațiilor finite, este echivalent cu studiul matricelor pătrate binare.

Digrafele pot fi îmbogățite în mai multe moduri, deseori sugerate de multiplele lor aplicații. În primul rând, avem digrame cu noduri și / sau arcuri echipate cu etichete sau numere distinctive (digrame colorate, digrame ponderate, pe noduri și / sau pe arcuri, ...). Aceste îmbogățiri timpurii găsesc, de asemenea, aplicații în domenii care variază de la chimie la fizica particulelor , de la probleme de transport la mecanica structurală , de la lingvistică la geografie .

Două îmbogățiri primare duc la structurile multi - grafice și multi - grafice . Îmbogățirea ulterioară a acestora duce la diferitele tipuri de automate deterministe și nedeterministe . Alte îmbogățiri duc la diagrame de programe și diagrame de flux , adică algoritmi . Prin intermediul unor grafice îmbogățite, este posibil să schematizați în mod util rețelele de calculatoare și rețelele paginilor Web care alcătuiesc site-urile, domeniile sau întreaga rețea globală.

Se consideră, de asemenea, variante de digrame care au o infinitate de noduri numărabilă și pe care le numim aici digrame infinite .

Bibliografie

( EN ) K. Thulasiraman, MNS Swamy (1992): Grafice: Teorie și algoritmi , John Wiley & Sons

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere digrafice

linkuri externe

Grafic regizat în MathWorld

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

V · D · M Combinatorial
Orientare generală	Combinatorică · Istoria combinatoriei · Matematică discretă · Secțiunea 05-XX din MSC
Noțiuni introductive	Permutații · Dispoziții · Combinații · Coeficienți binomiali · Partiții de numere întregi · Partiții de mulțimi finite - Identități și bijecții combinatorii
Configurări	Pătrat latin · pătrate magice · Desene Block · geometrii finite · Matroids - mozaicare · Polimini
Teoria graficelor	Copaci · Mers pe grafice ( Eulerian , Hamiltonian ) · Conexiune în grafice - grafice plane · Vopsirea graficelor și teorema celor patru culori ) · hipergrafe · Grafice și grupuri · digraf · Grafic al fluxului de numerar · Plimbări aleatorii pe grafice · omomorfismul graficelor · Algoritmi pe grafice
Combinatorie algebrică	Tabelul lui Young · funcții simetrice - serie de puteri formale · Funcții de generare · Polinoame ortogonale · Părți ale unui grup de structuri combinatorii - Aspecte algebră comutativă combinatorie
Alte domenii	Calculul umbrelor ( secvențe polinomiale de tip binomial · secvențe Sheffer ) - Combinatorial extremal