I grafi

Page 1

Assegnato un insieme X, con|X|≥ 2, verr` a denotato conP2(X) l’insieme dei sottoin- siemi di X di cardinalit` a 2. Definizione 1. Si dice grafo una terna ordinata G = ( V, L, ϕ), dove V ` e un insieme tale che|V|≥ 2, i cui elementi sono detti vertici o nodi, L ` e un insieme non vuoto, i cui elementi sono detti lati o archi, e ϕ : L→ P2(V ). Se l1, . . . , lh∈ L sono lati di G tali che ϕ(l1) =··· = ϕ(lh) ={v, w}∈ P2(V ), si dice che tra i vertici v e w c’` e unlato multiplo. Se ϕ ` e ingettiva, il grafoG si dice semplice. Nomenclatura SiaG = (V, L, ϕ) un grafo. Se l∈ L e ϕ(l) ={v, w}, si dice che v e w sono estremi di l e i due vertici v e w si dicono adiacenti. Un vertice che non sia estremo di alcun lato si dice isolato. Se due lati hanno un estremo in comune, allora si dice che sono incidenti. Infine, |V| si dice ordine diG. Osservazione 1. Viene esclusa da questa trattazione la possibilit` a di considerare il caso limite di grafi con vertici tutti isolati, perch´ e l’insieme dei lati ` e non vuoto. Inoltre viene escluso il caso che un vertice sia adiacente a se stesso, visto che l’applicazione ϕ ` e a valori in P2(V ). Nota Bene Nel seguito si considereranno esclusivamente grafi finiti, vale a dire con insieme dei vertici e insieme dei lati entrambi finiti. In tal caso i grafi possono essere rappresentati mediante un diagramma. Si osservi che ci sono diverse rappresentazioni di uno stesso grafo. Definizione 2. SianoG = ( V, L, ϕ) un grafo, v∈ V . Si dice grado o valenza di v il numero d(v) dei lati dei quali v ` e estremo. Un vertice si dicepari se il suo grado ` e pari, si dice dispari se il suo grado ` e dispari. Esempio 1. Si consideri il grafo G = (V, L, ϕ), dove V ={a, b, c}, L ={l1, l2, l3, l4, l5} e ϕ : L→ P2(V ) ` e cos` ı definita: ϕ(l1) = ϕ(l2) ={a, b}; ϕ(l3) =…