Drzewa rozpinające graf o danych stopniach wierzchołków
: 23 cze 2023, o 14:13
Szanowni forumowicze,
Mam do rozwiązania pewien problem z teorii grafów, jednak nie wiem jak się do niego zabrać. Po przeszukaniu internetu nie udało mi się znaleźć uniwersalnego rozwiązania, zatem proszę o pomoc Was.
Treść zadania:
Graf \(\displaystyle{ G = K_{14}}\) jest grafem pełnym o \(\displaystyle{ 14}\) ponumerowanych wierzchołkach.
1. Ile drzew rozpinających, w których nie ma wierzchołków stopnia większego od \(\displaystyle{ 2}\) ma ten graf?
2. Ile drzew rozpinających, w których każdy wierzchołek ma stopień \(\displaystyle{ 1}\) lub \(\displaystyle{ 4}\) ma ten graf?
Z góry dziękuję za pomoc.
Mam do rozwiązania pewien problem z teorii grafów, jednak nie wiem jak się do niego zabrać. Po przeszukaniu internetu nie udało mi się znaleźć uniwersalnego rozwiązania, zatem proszę o pomoc Was.
Treść zadania:
Graf \(\displaystyle{ G = K_{14}}\) jest grafem pełnym o \(\displaystyle{ 14}\) ponumerowanych wierzchołkach.
1. Ile drzew rozpinających, w których nie ma wierzchołków stopnia większego od \(\displaystyle{ 2}\) ma ten graf?
2. Ile drzew rozpinających, w których każdy wierzchołek ma stopień \(\displaystyle{ 1}\) lub \(\displaystyle{ 4}\) ma ten graf?
Z góry dziękuję za pomoc.