Glossari

Seleccioneu una de les paraules clau de l’esquerra ...

Gràfics i xarxesIntroducció

Temps de lectura: ~10 min
Aquesta pàgina ha estat traduïda automàticament i pot contenir errors. Poseu-vos en contacte si voleu ajudar-nos a revisar les traduccions.

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 gràfics (no s’han de confondre amb el gràfic d’una funció). Un gràfic està format per certs punts anomenats , algunes de les quals estan connectades per .

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 gràfics dirigits .

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 subgraf . Aquí podeu veure alguns exemples més de gràfics, amb vores i vèrtexs de colors que indiquen un possible subgraf:

Diem que l’ ordre d’un gràfic és el nombre de vèrtexs que té. El grau d'un vèrtex és el nombre d'arcs que es troben en aquest vèrtex.

Ordre:

Ordre:

Grau:

Titulació:

Els gràfics que consisteixen en un sol bucle de vèrtexs s’anomenen cicles . Tots els cicles tenen .

Equipat amb aquestes noves definicions, anem a explorar algunes de les fascinants propietats i aplicacions dels gràfics.