Shortest coverings of graphs with cycles (Q802571): Difference between revisions

Es wird bewiesen, daß jeder 2-fach kantenzusammenhängende, endliche Graph G ein System von Kreisen \(K_ 1,...,K_ m\) enthält, so daß jede Kante von G zu mindestens einem der Kreise \(K_ i\) gehört und \(\sum^{m}_{i=1}| K_ i| \leq \| G\| +\min \{2/3\| G\|,7/3(| G| -1)\}\) gilt, wobei \(| G|\) bzw. \(\| G\|\) die Ecken- bzw. Kantenzahl von G bedeute. Dies verschärft eine Abschätzung aus [\textit{A. Itai, R. J. Lipton, C. H. Papadimitriou} und \textit{M. Rodeh}: Covering graphs by simple circuits. SIAM J. Comput. 10, 746-750 (1981; Zbl 0468.68071)].