Witam, mam problem z zadaniem z matematyki dyskretnej. Prosiłbym o pomoc w miare możliwości.
Z góry dziękuje.
Iloczyn kartezjański grafów.
- arek1357
- 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.
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}\)
\(\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}\)