Grafy


Tematy pokrewne

Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie

Graf (ang. graph) jest powszechnie stosowaną strukturą danych we współczesnej informatyce. Pozwala on modelować wszelkiego rodzaju sieci oraz układy, w których występują skomplikowane zależności pomiędzy składnikami. Powstała cała teoria matematyczna, zwana Teorią Grafów (ang. Graph Theory), która zajmuje się tymi strukturami, ich własnościami oraz zasadami wykonywania na nich różnych działań. Za ojca grafów uważany jest Leonard Euler, szwajcarski matematyk, który dokonał bardzo wielu odkryć matematycznych, np. w rachunku różniczkowym i całkowym. W tym artykule zaprezentujemy podstawowe algorytmy grafowe, z którymi na pewno spotkasz się na studiach informatycznych. Również zadania Olimpiady Informatycznej w dużym stopniu bazują na teorii grafów, zatem jeśli chciałbyś wziąć udział w eliminacjach, to musisz tę teorię poznać. Wbrew pozorom, nie jest to wcale aż takie trudne.

Zapraszam do lektury.

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe