Grafo

Artikulu hau objektu matematiko buruzkoa da; beste esanahietarako, ikus Grafo (argipena).

6 erpin eta 7 ertzeko grafoa.

Grafoa, matematika eta konputazio zientzien ikuspuntutik, objektu multzo bat da, puntu edo erpin bitartez irudikatzen dena, objektu hauek lotzen dituzten lokarri edo ertzekin batera. Grafoak multzoaren elementuen arteko erlazio bitarrak irudikatzea ahalbidetzen du.

Definizioak

Grafoa G: = (V,E) formako bikote ordenatua da non:

• V puntu edo nodo multzo bat den.
• E lokarri edo ertz multzo bat den.

Normalean finitua izaten da. Grafo askoren emaitza garrantzitsuak ezin dira grafo infinituetan erabili. Grafoaren ordenak puntu edo nodo kopuruak zehazten du.

Begiztak

Begizta bat puntu berdina erlazionatzen duen ertza da.

Grafo ez zuzendua

Grafo ez zuzendua.

$G = (V, E)$ grafo ez zuzenduak (edo grafo ez-orientatua) ondorengoa betetzen du:

• $V\neq\emptyset$
• $E\subseteq \{x\in\mathcal P(V): |x|=2\}$, $V\,$-ren elementuen ordenatu gabeko bikote multzoa da.

Ordenatu gabeko bikoteak $\{a, b\}$ formako multzoa da, non $\{a, b\}=\{b, a\}$ den. Multzo hauek 2 kardinaleko $V$-ren potentzia-multzoarena da, matematikoki $\mathcal P(V)$ bezala adierazten dena.

Grafo zuzendua

Grafo zuzendua.

$G = (V, E)$ grafo zuzenduak (edo grafo orientatua) ondorengoa betetzen du:

• $V\neq\emptyset$
• $E \subseteq \{(a,b) \in V \times V: a \neq b \}\,$, $V\,$-ren elementuen bikote ordenatu multzoa da.

$(a,b)$ erpinak emanik, non $a$ hasierako erpina eta $b$ amaierako erpina den.

Definizioz, grafo zuzenduek ezin dute begiztarik eduki.

Ikus, gainera

• Grafo teoria