Witajcie! Mam tutaj parę zadań i niespecjalnie wiem jak sobie z nimi poradzić.
zadanie 1.
Ile krawędzi ma graf:
a) \(\displaystyle{ P_{n}\left[C_{n}\right]}\)
b) \(\displaystyle{ C_{n}\left[P_{n}\right]}\)
c) \(\displaystyle{ K_{m,n}}\)
d) \(\displaystyle{ C_{n} \times C_{m}}\)
zadanie 2.
Ile jest grafów n-wierzchołkowych takich, że wierzchołki 1,2,3 są trzeciego stopnia i
a) nie mogą być sąsiednie
b) mogą być sąsiednie
Czy ktokolwiek może mnie nakierować jak się w ogóle za tego typu zadania zabierać? Profesor twierdził, że są to zadania na 30 sekund.
Ilość krawędzi / grafów
-
sebnorth
- Użytkownik
- Posty: 635
- Rejestracja: 12 sty 2011, o 16:27
- Płeć: Mężczyzna
- Lokalizacja: Puck i Trójmiasto
- Pomógł: 201 razy
Ilość krawędzi / grafów
c) to chyba pełny graf dwudzielny zatem ma \(\displaystyle{ m \cdot n}\) krawędzi
d) to zależy co rozumiemy przez krzyżyk, jeśli rozumiemy graf którego zbiór wierzchołków \(\displaystyle{ V = V_{C_n} \times V_{C_{m}}}\) (kartezjańsko) a zbiór krawędzi \(\displaystyle{ E = \{((a,b),(c,d)) : a,c \in V_{C_n}, b,d \in V_{C_m}, (a,c) \in E_{C_n}, (b,d) \in E_{C_m} \}}\) to \(\displaystyle{ |E| = |E_{C_n}| \cdot |E_{C_m}| = n \cdot m}\).
a), b) nie pamiętam tych oznaczeń
2a)
wszystkich krawędzi jest \(\displaystyle{ {n \choose 2}}\), zostało użytych 9 z nich, mamy więc do zagospodarowania \(\displaystyle{ {n \choose 2} - 9}\) krawędzi. Wyborów zbioru krawędzi jest tyle ile jest podzbiorów zbioru \(\displaystyle{ {n \choose 2} - 9}\) elementowego, czyli \(\displaystyle{ 2^{{n \choose 2} - 9}}\).
d) to zależy co rozumiemy przez krzyżyk, jeśli rozumiemy graf którego zbiór wierzchołków \(\displaystyle{ V = V_{C_n} \times V_{C_{m}}}\) (kartezjańsko) a zbiór krawędzi \(\displaystyle{ E = \{((a,b),(c,d)) : a,c \in V_{C_n}, b,d \in V_{C_m}, (a,c) \in E_{C_n}, (b,d) \in E_{C_m} \}}\) to \(\displaystyle{ |E| = |E_{C_n}| \cdot |E_{C_m}| = n \cdot m}\).
a), b) nie pamiętam tych oznaczeń
2a)
wszystkich krawędzi jest \(\displaystyle{ {n \choose 2}}\), zostało użytych 9 z nich, mamy więc do zagospodarowania \(\displaystyle{ {n \choose 2} - 9}\) krawędzi. Wyborów zbioru krawędzi jest tyle ile jest podzbiorów zbioru \(\displaystyle{ {n \choose 2} - 9}\) elementowego, czyli \(\displaystyle{ 2^{{n \choose 2} - 9}}\).