Gràfics i xarxesIntroducció
Cada dia ens envolten infinitat de connexions i xarxes: carreteres i vies ferroviàries, línies telefòniques, internet, circuits electrònics i fins i tot enllaços moleculars. Fins i tot hi ha xarxes socials entre amics i famílies. Pot pensar en altres exemples?
Xarxes viàries i ferroviàries
Xips d’ordinador
Cadenes de subministrament
Amistats
Connexions neuronals
Internet
En matemàtiques, tots aquests exemples es poden representar com a
La teoria de gràfics és l'estudi dels gràfics i de les seves propietats. És una de les àrees visuals més emocionants i visuals de les matemàtiques i té infinitat d'aplicacions importants.
Podem dibuixar la disposició de gràfics senzills mitjançant cercles i línies. La posició dels vèrtexs i la longitud de les vores és irrellevant; només ens importa la forma de connectar -se entre ells. Les vores fins i tot es poden creuar entre si i no han de ser rectes.
En alguns gràfics, les vores només van d’un sol sentit. S’anomenen
Alguns gràfics consisteixen en diversos grups de vèrtexs que no estan connectats entre si per arestes. Aquests gràfics estan desconnectats .
Altres gràfics poden contenir múltiples vores entre els mateixos parells de vèrtexs o vèrtexs connectats a ells mateixos (bucles).
Podem crear gràfics nous a partir d’un gràfic existent eliminant alguns dels vèrtexs i les vores. El resultat s’anomena
Diem que l’
Ordre:
Ordre:
Grau:
Titulació:
Els gràfics que consisteixen en un sol bucle de vèrtexs s’anomenen
Equipat amb aquestes noves definicions, anem a explorar algunes de les fascinants propietats i aplicacions dels gràfics.