Bipartitní graf

Abstract

Další ze série článků věnovaných úlohám Matematické olympiády - kategorie P (programování) ukazuje dvě starší soutěžní úlohy z let 1993 a 1997 s odlišným zadáním, ale téměř shodným způsobem řešení. Zatímco jedna úloha pojednává o silniční síti, druhá se zabývá vzájemnými známostmi hostů na večírku. V obou úlohách ale ve skutečnosti zjišťujeme, zda je doplněk zadaného neorientovaného grafu bipartitní. Druhá z úloh se jen drobně liší tím, že navíc určujeme počet možností, jak je možné rozdělit vrcholy grafu do dvou skupin. Článek vysvětluje algoritmus, ukazuje jeho časovou složitost a také jeden možný způsob implementace.

The article from the series dedicated to problems of Mathematical Olympiad - category P (programming) shows two older competition tasks from 1993 and 1997 with different assignments, but almost identical solutions. While one task deals with the road network, the other deals with the relations of the guests at the party. In both tasks, however, we actually determine whether the complement of the given undirected graph is bipartite. The second of the tasks differs only slightly in that we also determine the number of options for dividing the vertices of the graph into two groups. The article explains the algorithm, shows its time complexity and also one possible way of implementation.