La teoria dei grafi è lo studio di punti e linee. In particolare, riguarda i modi in cui gli insiemi di punti, chiamati vertici, possono essere collegati da linee o archi, chiamati bordi. I grafici in questo contesto differiscono dai grafici di coordinate più familiari che rappresentano le relazioni e le funzioni matematiche.
I grafici sono classificati in base alla loro complessità, al numero di bordi consentiti tra due vertici qualsiasi e all'assegnazione o meno di direzioni (ad esempio, su o giù) ai bordi. Vari insiemi di regole danno luogo a proprietà specifiche che possono essere dichiarate come teoremi.
La teoria dei grafi si è dimostrata utile nella progettazione di circuiti integrati (CI) per computer e altri dispositivi elettronici. Questi componenti, più spesso chiamati chip, contengono microcircuiti complessi a strati che possono essere rappresentati come insiemi di punti interconnessi da linee o archi. Utilizzando la teoria dei grafi, gli ingegneri sviluppano chip con la massima densità dei componenti e la minima lunghezza totale dei conduttori di interconnessione. Questo è importante per ottimizzare la velocità di elaborazione e l'efficienza elettrica.