Cos'è arista?

Arista (Grafi)

In teoria dei grafi, un'arista (o lato) è una connessione tra due vertici in un grafo. Formalmente, un'arista è una coppia di vertici.

  • Definizione: Un'arista e in un grafo G = (V, E) è una coppia non ordinata (u, v), dove u, v ∈ V e E rappresenta l'insieme delle ariste.

  • Tipi di Ariste:

    • Arista non orientata: Rappresenta una connessione bidirezionale tra due vertici. L'arista (u, v) è equivalente all'arista (v, u).
    • Arista orientata: Rappresenta una connessione unidirezionale tra due vertici. L'arista (u, v) è diversa dall'arista (v, u). In questo caso, l'arista è anche chiamata arco.
  • Incidenza: Un'arista e = (u, v) è detta incidente sui vertici u e v.

  • Adiacenza: Due vertici u e v sono detti adiacenti se esiste un'arista che li connette. Due ariste sono dette adiacenti se condividono un vertice.

  • Ariste Multiple (o Ariste Parallele): Se più di un'arista connette gli stessi due vertici, queste sono chiamate ariste multiple o parallele. I grafi che permettono ariste multiple sono chiamati multigrafi.

  • Cappio (o Anello): Un'arista che connette un vertice a se stesso è chiamata cappio o anello. Un'arista (u, u) è un cappio incidente sul vertice u.

L'esistenza o meno di cappi e ariste multiple influenza il tipo di grafo che si sta considerando. Un grafo che non contiene né cappi né ariste multiple è detto grafo semplice.