matematykaszkolna.pl
Pseudolasem nazywamy graf, którego każda składowa spójna zawiera co najwyżej jed Karmel: Pseudolasem nazywamy graf, którego każda składowa spójna zawiera co najwyżej jeden cykl. Ile krawędzi może mieć pseudolas mający n wierzchołków oraz s składowych spójnych?
10 wrz 17:22
kerajs: Graf spójny bez cykli o k wierzchołkach ma k−1 krawędzi. Graf spójny 1 jednym cyklem i o k wierzchołkach ma k krawędzi. Stąd, dla s≤n pseudolas, może mieć od n−s do n krawędzi.
10 wrz 17:54