D 2014

Problem of searching minimum spanning tree

ANTOŠ, Karel

Základní údaje

Originální název

Problem of searching minimum spanning tree

Název česky

Problém hledání minimální kostry grafu

Autoři

Vydání

1. vyd. Liberec, Proceedings of International Conference Presentation of Mathematics `14, od s. 7-16, 10 s. 2014

Nakladatel

Technická univerzita v Liberci

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

paměťový nosič (CD, DVD, flash disk)

Organizační jednotka

Vysoká škola technická a ekonomická v Českých Budějovicích

ISBN

978-80-7494-108-5

Klíčová slova česky

: teorie grafů; minimální kostra grafu; Joseph Kruskal; hladový algoritmus

Klíčová slova anglicky

graph theory; minimum spanning tree; Joseph Kruskal; reverse algorithm

Štítky

Změněno: 7. 10. 2014 10:10, Mgr. Václav Karas

Anotace

V originále

This article provides solutions to certain models of graph theory, where the minimum spanning tree (MST) models are suitable. The principle of the MST problem is the fact that it is necessary to find the model situations for which this method is suitable, to find how to use this method in finding a solution, and finally to compare two methods of looking for the MST, in terms of their different approaches, their complementarity, and their assessment, which of these two methods can find a feasible solution faster in particular cases. A theoretical discussion and a model example are carried out to compare the two methods.

Česky

Tento článek poskytuje řešení pro některé modely z teorie grafů, pro které je nástroj minimální kostry (MKG) vhodný. Princip problému MKG je v tom, že je třeba nalézt modelové situace, pro které je tato metoda vhodná, a dále zjistit, jak použít tuto metodu při hledání řešení, a nakonec porovnat dva způsobyhledání MKG, z hlediska jejich rozdílného přístupu, jejich doplňování se a jejich hodnocení, dále která z těchto dvou metod můžete najít možné řešení rychleji a ve kterých konkrétních případech. Teoretické diskuse a modelový příklad jsou provedeny za účelem porovnání těchto dvou metod.