Niech X= {1,....,9}. Wierzcholkami grafu G=(V ,E) sa wszystkie 3-elementowe podzbiory zbioru X a dwa wierzcholki A,B \(\displaystyle{ \in}\) V laczy krawedzia wtedy i tylko wtedy gdy |A \(\displaystyle{ \cap}\) B | =1.
1. znajdz rziad i rozmiar grafu G oraz wyznacz wszystkie mozliwe wartosci przyjmowane jako stopnie wierzcholkow w grafie G
2. Czy G jest grafem dwudzielnym?
Wszystkie odp uzasadnij.
Bardzo prosze o pomoc, zadanie z Matematyki Dyskretnej na AGH.
grafy rzad, rozmiar, dwudzielny
-
danielek12201220
- Użytkownik
- Posty: 8
- Rejestracja: 24 mar 2017, o 17:23
- Płeć: Mężczyzna
- Lokalizacja: Kraków
-
mCichy13
- Użytkownik
- Posty: 76
- Rejestracja: 15 cze 2013, o 02:20
- Płeć: Mężczyzna
- Lokalizacja: Tutaj
- Podziękował: 26 razy
- Pomógł: 5 razy
grafy rzad, rozmiar, dwudzielny
Wszystkich możliwych wierzchołków jest:
\(\displaystyle{ {9 \choose 3} = 84}\)
To chyba nie wymaga tłumaczenie.
Pkt 2
Nie jest. Wystarczy pokazać że graf posiada cykl o nieparzystej długości.
\(\displaystyle{ \left(1,2,3\right),\left(1,4,5\right),\left(1,6,7\right) \in V}\) i są połączone krawędziami.
Pkt1
Maksymalny stopień wierzchołka to 45 i to jedyny możliwy stopień. Ponieważ
wierzchołek np \(\displaystyle{ \left( 1,2,3\right)}\) będzie połączony z wszystkimi wierzchołkami które zawierają 1 i nie zawierają 2 i 3.
\(\displaystyle{ \left( X,Y,Z\right)}\)
X -> tutaj będzie 1
natomiast \(\displaystyle{ \left( X,Y\right)}\) to wszystkie możliwe podzbiory zbioru\(\displaystyle{ \left\{ 4,5,6,7,8,9\right\}}\) . Reasumujący wynik to \(\displaystyle{ 1* {6 \choose 2} = 15}\). Oczywiście dla 2 i 3 też będzie 15 możliwości więc sumarycznie wyjdzie 45.
Jeśli chodzi o rząd i rozmiar to nie znam ich definicji.
\(\displaystyle{ {9 \choose 3} = 84}\)
To chyba nie wymaga tłumaczenie.
Pkt 2
Nie jest. Wystarczy pokazać że graf posiada cykl o nieparzystej długości.
\(\displaystyle{ \left(1,2,3\right),\left(1,4,5\right),\left(1,6,7\right) \in V}\) i są połączone krawędziami.
Pkt1
Maksymalny stopień wierzchołka to 45 i to jedyny możliwy stopień. Ponieważ
wierzchołek np \(\displaystyle{ \left( 1,2,3\right)}\) będzie połączony z wszystkimi wierzchołkami które zawierają 1 i nie zawierają 2 i 3.
\(\displaystyle{ \left( X,Y,Z\right)}\)
X -> tutaj będzie 1
natomiast \(\displaystyle{ \left( X,Y\right)}\) to wszystkie możliwe podzbiory zbioru\(\displaystyle{ \left\{ 4,5,6,7,8,9\right\}}\) . Reasumujący wynik to \(\displaystyle{ 1* {6 \choose 2} = 15}\). Oczywiście dla 2 i 3 też będzie 15 możliwości więc sumarycznie wyjdzie 45.
Jeśli chodzi o rząd i rozmiar to nie znam ich definicji.