Glosar

Selectați unul dintre cuvintele cheie din stânga ...

Grafice și rețeleIntroducere

Timp de citit: ~10 min

În fiecare zi suntem înconjurați de nenumărate conexiuni și rețele: drumuri și căi ferate, linii telefonice, internet, circuite electronice și chiar legături moleculare. Există chiar și rețele sociale între prieteni și familii. Vă puteți gândi la alte exemple?

Rețele rutiere și feroviare

Chipuri de calculator

Lanțurile de aprovizionare

prieteniile

Conexiuni neuronale

Internetul

În matematică, toate aceste exemple pot fi reprezentate ca grafice (nu trebuie confundate cu graficul unei funcții). Un grafic este format din anumite puncte numite , unele dintre ele fiind conectate prin .

Teoria graficului este studiul graficelor și a proprietăților acestora. Este una dintre cele mai interesante și vizuale domenii ale matematicii și are nenumărate aplicații importante.

Putem realiza aspectul graficelor simple folosind cercuri și linii. Poziția vârfurilor și lungimea marginilor este irelevantă - ne interesează doar modul în care acestea sunt conectate între ele. Marginile se pot încrucișa și nu trebuie să fie drepte.

În unele grafice, marginile merg doar într-un singur sens. Acestea se numesc grafice direcționate .

Unele grafice constau din mai multe grupuri de vârfuri care nu sunt conectate între ele prin margini. Aceste grafice sunt deconectate .

Alte grafice pot conține mai multe muchii între aceleași perechi de vârfuri sau vârfuri care sunt legate între ele (bucle).

Putem crea noi grafice dintr-un grafic existent eliminând unele dintre vârfuri și muchii. Rezultatul se numește subgrafă . Aici puteți vedea câteva alte exemple de grafice, cu margini colorate și vârfuri care indică o posibilă subgrafă:

Spunem că ordinea unui grafic este numărul de vârfuri pe care le are. Gradul unui vertex este numărul de muchii care se întâlnesc la acel vertex.

Comanda:

Comanda:

Grad:

Grad:

Graficele care constau dintr-o singură buclă de vârfuri se numesc cicluri . Toate ciclurile au .

Dotat cu aceste noi definiții, să explorăm unele dintre proprietățile și aplicațiile fascinante ale graficelor.