Network Principles Flashcards
Definisci una Rete Orientanta
Una rete orientanta è una rete definita da un insieme di nodi e di archi i quali sono costituiti da coppie ordinate di nodi distinti.
Cosa si intende per grado di un Nodo?
Il grado di un nodo esprime la somma del indegree e outdegree
Cos’è un sottografo?
Un sottografo è un grafo G’ i cui elementi A’ e N’ sono due sottoinsiemi di di G=(A,N)
Definisci un cammino
Un cammino è un sottografo con una sequenza di nodi consecutivi.(Sono permesse ripetizioni dei nodi)
Definisci un percorso
Un percorso è un cammino senza ripetizioni dei nodi
Cos ‘è un ciclo?
Un ciclo è un percorso in cui l’ultimo nodo coincide con il primo.
Quando un grafo è connesso?
Un grafo si dice connesso se tutte le coppie di nodi sono connesse. Due nodi sono connessi se esiste almeno un percorso che li unisce.
Cos’è un taglio?
Un taglio è una partizione dell’insieme dei nodi in due insiemi S e S^. Definisce un insieme di archi aventi un estremo in S e l’altro in S^.
Cos’è un ciclo Hamiltoniano?
E’ un percorso o ciclo che visita tutti i nodi della rete una sola volta.
Che proprietà ha la matrice di adiacenza nodo arco
Rappresenta una rete come la matrice dei vincoli di un MCFP. La matrice è nxm che contiene una riga per ogni nodo e una colonna per ogni arco.La colonna corrispondente a (i,j) possiede solo due elementi: +1 nella riga corrispondente a i e -1 in quella di j
