Iloczyn kartezjański grafów.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
mike866
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 10 paź 2013, o 12:35
Płeć: Mężczyzna
Lokalizacja: Wrocław

Iloczyn kartezjański grafów.

Post autor: mike866 »

Witam, mam problem z zadaniem z matematyki dyskretnej. Prosiłbym o pomoc w miare możliwości.



Z góry dziękuje.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Iloczyn kartezjański grafów.

Post autor: arek1357 »

Iloczyn kartezjański grafów to zbiór wierzchołków typu:

\(\displaystyle{ (a_{i},b_{j})}\) oraz krawędzi typu:

\(\displaystyle{ [(x_{1},x_{2});(y_{1},y_{2})]}\)

gdzie:

\(\displaystyle{ [(x_{1}=y_{1})] \vee [(x_{2}=y_{2})]}\)

i sobie tworzysz krawędzie u siebie w ten sposób:

\(\displaystyle{ \overline{[(a_{1},b_{1});(a_{1},b_{2})]} ; \overline{[(a_{1},b_{1});(a_{2},b_{1})]},...}\)

gdzie oczywiście pary:

\(\displaystyle{ [(b_{1},b_{2}]}\)

\(\displaystyle{ [(a_{1},a_{2}]}\)

są krawędziami w źródłowych grafach.

Wierzchołków w twoim przykładzie będzie:

\(\displaystyle{ 3 \cdot 5=15}\)

krawędzi będzie:

\(\displaystyle{ 3 \cdot 5+5 \cdot 2=25}\)
ODPOWIEDZ