Zad 1 . Tabela zawiera krawędzie grafu nieskierowanego o 7 wierzchołkach posortowane w/g wag. Metoda Kruskala wyznaczyć najmniejsze drzewo rozpinające i jego wagę. w Kolumnie Krawędz > dod? wpisać 1 gdy krawędź dodana 0 gdy odrzucona Podać Macierz wag
(Ja nie wiem o co Tu chodzi macierz wag łatwo mi jest zrobić ale jak tabelkę wypełnić to ja nie mam pojęcia wytłumaczcie mi to bo ja już nie mogę ;/)
\(\displaystyle{ \begin{tabular}{|c||c||c||c||c||c||c||c||c||c||c||c|} \hline
{L.p} & \multicolumn{4}{|c|}{Krawedz} & \multicolumn{7}{|c|}{Numery zbiorow dla wierzcholkow} \\
\hline
& V1 & V2 & waga & dod? & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
1 & 1 & 7 & 5 &&&&&&&&\\
2 & 2 & 4 & 7 &&&&&&&& \\
3 & 2 & 5 & 10 &&&&&&&& \\
4 & 3 & 5 & 10 &&&&&&&& \\
5 & 3 & 4 & 12 &&&&&&&& \\
6 & 4 & 5 & 14 &&&&&&&& \\
7 & 3 & 6 & 18 &&&&&&&& \\
8 & 2 & 7 & 20 &&&&&&&&\\
9 & 1 & 2 & 22 &&&&&&&& \\
10 & 4 & 6 & 25 &&&&&&&& \\ \hline
\end{tabular}}\)
waga=
zad 2. x,y są dowolnymi liczbami całkowitymi z przedziału domkniętego [1,100].
Tworzymy zbiory wszystkich par tych licz i wyróżniamy zbiory
\(\displaystyle{ A={(x,y); 9|x , y \ dowolne}, B={(x,y); x \ dowolne 12|y}, (a|b a - jest dzielnikiem b)}\)
Wyznaczyć liczebność zbiorów (tu wpisać odpowiedzi , \(\displaystyle{ \AA}\) oznacza dopełnienie zbioru A)
\(\displaystyle{ |A|= \ |B|= \ [A \cap B|= \ [A \cup B]= \ [A' \cap B'] =}\)
zad3.
Dana jest Macierz grafu skierowanego
\(\displaystyle{ \begin{tabular}{|c||c||c||c||c||c||c||c|}
\hline
& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline
1 & 0 & 10 & 15 & 20 & 18 & 13 & 23 \\ \hline
2 & 12 & 0 & 17 & 19 & 31 & 14 & 27 \\ \hline
3 & 16 & 21 & 0 & 25 & 11 & 14 & 29 \\ \hline
4 & 21 & 23 & 19 & 0 & 13 & 9 & 17 \\ \hline
5 & 20 & 29 & 13 & 15 & 0 & 26 & 16 \\ \hline
6 & 15 & 28 & 17 & 12 & 23 & 0 & 18 \\ \hline
7 & 23 & 27 & 19 & 17 & 15 & 19 & 0 \\ \hline
\end{tabular}}\)
Macierz sąsiedztwa
\(\displaystyle{ \begin{tabular}{|c||c||c||c||c||c||c||c|}
\hline
& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline
1 & x & & 1 & 1 & & 1 & 1 \\ \hline
2 & & x & 1 & & 1 & & \\ \hline
3 & 1 & 1 & x & 1 & & 1 & 1 \\ \hline
4 & 1 & & 1 & x & 1 & & 1 \\ \hline
5 & & 1 & & 1& x & 1 & \\ \hline
6 & 1 & & 1 & & 1 & x & 1 \\ \hline
7 & 1 & & 1 & 1 & & 1 & x \\ \hline
\end{tabular}}\)
Poszukujemy drogi komiwojażera metodą dołączania najdalszego wierzchołka (start z 1 ) Mając wyniki uzyskane po 3 iteracjach wykonać 4-tą iterację (kolumny; cykl ,waga ,dist - wypełnić tylko dla wybranego )
\(\displaystyle{ \begin{tabular}{|c||c||c||c||c||c||c||c||c||c||c||c||c||c||c||c||c|} \hline
{Iter.} & {f} & {i,j} & {koszt [c,j]} & {wybrane x} & {cykl} & {waga} &\multicolumn{7}{|c|}{Dist} \\
\hline
& & & & &&& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
...& ... & ...& - & & & & & & & & & & \\ \hline
3 & 3 & 71 & 12=19+16-23 &&14731&72&-&10&-&-&11&9&-\\\hline
& & & &&&&&&&&&& \\
& & & &&&&&&&&&& \\
4 & & & &&&&&&&&&& \\
& & & &&&&&&&&&& \\
& & & &&&&&&&&&& \\ \hline
\end{tabular}}\)
Dla grafu nieskierowanego z macierzą sąsiedztwa przeprowadzić kolorowanie wierzchołków stosując przy tym prosty algorytm sekwencyjny
(kolory jako liczby 1-czerwony, 2-zielony, 3- niebieski)
\(\displaystyle{ \begin{tabular}{|c||c||c||c||c||c||c||c|}
\hline
V& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline
sąsiedzi pokolorow. & & & & & & & \\ \hline
kolory sąsiadów & & & & & & & \\ \hline
kolory v & & & & & & & \\ \hline
\end{tabular}}\)
Dziękuję od razu wszystkim którzy będą mi pomagać
Problem z grafami
Problem z grafami
no ale z przeczytania nic mi to nie da ja tego nie kapuje w ogole znalazlby sie ktos taki mily i pomogl mi