Algorithms for finding the strongly connected components of directed graphs
ID LANG, INA (Avtor), ID Dobravec, Tomaž (Mentor) Več o mentorju...

 PDF - Predstavitvena datoteka, prenos (2,01 MB)MD5: F2E983C96BADF072DF04402B1DAA564F

Izvleček
One of the most common problems in graph theory is the problem of finding strongly connected components (SCCs). Decomposing a directed graph into strongly connected components is a fundamental tool in graph theory with applications in compiler analysis, data mining, scientific computing, and other areas. In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex in that graph. The strongly connected components of an arbitrary directed graph form a partition into subgraphs. Those subgraphs are themselves strongly connected. In this bachelor thesis, we will introduce the problem mentioned above in detail. We will try to understand its importance by looking at its applications. Then we will proceed exploring different approaches for finding strongly connected components of a directed graph. Finally, we will inspect their advantages and disadvantages by comparing them and draw a conclusion as to which algorithm performs best in a given situation.

Jezik: Angleški jezik graph, strong connectivity, strongly connected, Tarjan’s algorithm, Kosaraju’s algorithm, Gabow, path-based, Blelloch, Fleischer, parallelism. Diplomsko delo/naloga (mb11) 2.11 - Diplomsko delo FRI - Fakulteta za računalništvo in informatiko 2021 20.500.12556/RUL-130334 77685251 13.09.2021 368 43 Kopiraj citat AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.Uredi privoljenje...

## Sekundarni jezik

Jezik: Slovenski jezik Algoritmi za iskanje močno povezanih komponent usmerjenih grafov Eden od najpogostejših problemov v teoriji grafov je problem iskanja močno povezanih komponent usmerjenega grafa. Razgradnja samega usmerjenega grafa v močno povezane komponente predstavlja pomembno orodje v teoriji grafov, ki je uporabno pri analizi prevajalnikov, podatkovnem rudarjenju in na ostalih področjih. V matematični teoriji pravimo, da je graf močno povezan, če za vsaki dve njegovi vozlišči velja, da sta dosegljivi med seboj. Prav tako mora za vsako od močno povezanih komponent poljubnega usmerjenega grafa veljati, da tudi sama predstavlja močno povezan graf. V tem diplomskem delu bomo podrobno predstavili zgoraj omenjeni problem. Preko njegove aplikacije bomo poskušali razumeti njegov pomen. Nato bomo raziskali različne pristope za iskanje močno povezanih komponent usmerjenih grafov. Na koncu bomo s primerjavo preučili njihove prednosti in pomanjkljivosti ter iz tega sklepali, kateri algoritem je ustrezen v določeni situaciji. graf, močna povezanost, močno povezane komponente, Kosaraju, Tarjan, Gabow, Blelloch, Fleischer, vzporednost.

Nazaj