AS Matlab - Solutions
Algoritmy na sietach 2021, online
Contents
- Riesene ulohy
- Uloha 0: Priprava
- Uloha 1: Vytvorte neorientovany graf s nahodne generovanymi hranami
- Uloha 2: Priemerny pocet hran v nahodnom grafe
- Uloha 3: Zoznam hran
- Uloha 4: Vizualizacia grafu
- Uloha 5: Orientovany graf
- Uloha 6: Orientovany graf s vahami
- Uloha 7: Zmena vzhladu grafu
- Uloha 8: Text oznacenia vrcholov
- Uloha 9: Podgraf
Riesene ulohy
Uloha 0: Priprava
Vytvorte novy subor s nazvom grafy.m a ulozte ho do adresara grafy_matlab, ktory si predtym vytvorite.
Uloha 1: Vytvorte neorientovany graf s nahodne generovanymi hranami
Nastavte pracovny adresar na adresar, ktory tento subor obsahuje. Vytvorte premennu vertices so zoznamom vrcholov grafu, ocislovanych od 1 po 10. Vytvorte premennu M, ktora bude maticou susednosti k tomuto neorientovaneho grafu s nahodnymi hranami tak, ze vrcholy i a j su spojene neorientovanou hranou s pravdepodobnostou 0.3. Zobrazte maticu susednosti a zisti pocet hran.
vertices = 1:10; % vrcholy n = numel(vertices); % pocet vrcholov M = rand(n,n); % nahodna matica s rozdelenim U([0,1]) M = tril(double(M<0.3),-1); % dolna trojuholnikova matica bez diagonaly M = M + transpose(M); % symetrizacia matice M - preklopenie jej prvkov nad diagonalu m = sum(sum(tril(M))); % pocet hran v grafe disp(M) % vypise maticu susednosti disp(m) % vypise pocet hran
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 13
Uloha 2: Priemerny pocet hran v nahodnom grafe
Kolko hran v priemere by ste mali dostat v predoslom priklade? Overte, ze vysledok je spravny volbou ovela vacsieho grafu.
p = 0.3; % pravdepodobnost hrany vertices = 1:1000; % vrcholy n = numel(vertices); % pocet vrcholov M = rand(n,n); % nahodna matica s rozdelenim U([0,1]) M = tril(double(M<p),-1); % dolna trojuholnikova matica bez diagonaly M = M + transpose(M); % symetrizuj m = sum(sum(tril(M))); % pocet hran fprintf(1,'\nPocet hran %d z maximalneho poctu %d, percento %1.4f\n',m,n*(n+1)/2,2*m/n/(n+1))
Pocet hran 149596 z maximalneho poctu 500500, percento 0.2989
Uloha 3: Zoznam hran
Najdite zoznam vsetkych hran i<->j ako zoznam dvojic [i,j]
vertices = 1:10; % vrcholy n = numel(vertices); % pocet vrcholov M = rand(n,n); % nahodna matica s rozdelenim U([0,1]) M = tril(double(M<0.3),-1); % dolna trojuholnikova matica bez diagonaly M = M + transpose(M); % symetrizuje maticu [col,row] = find(M); % najde nenulove prvky matice M edges = [row,col]; % ulozi vychadzajuci a vchadzajuci vrchol pre kazdu hranu do premennej edges disp(edges) % vypise premennu edges disp(M) % vypise M
1 5 1 9 2 3 2 8 2 10 3 2 3 5 3 10 4 5 4 8 4 10 5 1 5 3 5 4 5 7 5 9 6 9 6 10 7 5 7 10 8 2 8 4 9 1 9 5 9 6 10 2 10 3 10 4 10 6 10 7 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0
Uloha 4: Vizualizacia grafu
Definujte grafovu strukturu v Matlabe pre vyssie vygenerovany graf. Zobrazte graf pomocou prikazu plot. Vyhladajte, ako prikaz funguje, zadanim help plot do prikazoveho riadku.
G = graph(M~=0); % definuje graf pomocou matice susednosti G.Edges % vypise vsetky hrany help graph/plot % najde help k vykreslovaniu grafov plot(G,'-.','NodeColor','red','EdgeColor',[0 0.6 0],'layout','force') % vykresli graf a skus zmenit rozne parametre
ans = EndNodes ________ 1 5 1 9 2 3 2 8 2 10 3 5 3 10 4 5 4 8 4 10 5 7 5 9 6 9 6 10 7 10 PLOT Plots an undirected graph PLOT(G) plots the undirected graph G. PLOT(G,LINESPEC) plots the undirected graph G using the color, marker and line style specified by the character string LINESPEC. For example, use 'ro--' to plot red circles as nodes and red dashed lines as edges. PLOT(G,...,'Layout',L) plots the graph G using the layout method specified by the string L, which must be one of the following: 'auto' (Default) Automatic choice of layout method based on the structure of the graph. 'circle' Circular layout. 'force' Force-directed layout. Uses attractive and repulsive forces on nodes. 'layered' Layered layout. Places nodes in a set of layers. 'subspace' Subspace embedding layout. Uses projection onto an embedded subspace. 'force3' 3-D force-directed layout. 'subspace3' 3-D Subspace embedding layout. PLOT(G,...,'XData',X,'YData',Y) plots the graph G by placing nodes at the coordinates specified by the vectors X and Y of length NUMNODES(G). PLOT(G,...,'XData',X,'YData',Y,'ZData',Z) plots the graph G in 3-D, by placing nodes at the coordinates specified by the vectors X, Y and Z of length NUMNODES(G). PLOT(AX,...) plots into the axes with handle AX. H = plot(...) also returns a GraphPlot object. Use the methods and properties of this object to inspect and adjust the plotted graph. The previous syntaxes can also contain one or more Name-Value pair arguments that specify additional properties of the GraphPlot object. Example: % Construct and plot an undirected graph. G = graph(bucky) plot(G) Example: % Construct and plot a graph. Use Name-Value pair arguments to % set the color of the nodes and edges. G = graph(bucky) plot(G,'NodeColor','red','EdgeColor',[0 0.6 0]) Example: % Construct and plot a graph. Return the GraphPlot object H. % Adjust the plotted graph by changing different properties of H. G = graph(bucky) H = plot(G) H.NodeColor = 'red' H.EdgeColor = [0 0.6 0] See also GRAPH, matlab.graphics.chart.primitive.GraphPlot Reference page in Doc Center doc graph/plot
Uloha 5: Orientovany graf
Vytvorte orientovany graf bez zluciek s 10 vrcholmi a nahodnymi hranami, kazda s pravdepodobnostou 0.3. Pridajte kazdej hrane vahu, ktora bude nahodne prirodzene cislo medzi 1-10.
vertices = 1:10; % vrcholy n = numel(vertices); % pocet vrcholov M = rand(n,n); % nahodna matica s rozdelenim U([0,1]) M = double(M<0.3); % definuje hrany v orientovanom grafe podla pravdepodobnostneho pravidla M = randi([1,10],n).*M; % definuje nahodne vahy hran M = M-diag(diag(M)); % nahradi nenulove cisla na diagonale nulami [col,row] = find(M); % najde vsetky hrany edges = [row,col]; % definuje hrany grafu pomocou vychadzajucich a vchadzajucich vrcholov disp([col,row]) % vypise tuto maticu G = digraph(M~=0); % definuje orientovany graf plot(G,'NodeColor','red','EdgeColor',[0 0.6 0]) % zobrazi orientovany graf
5 1 6 2 9 2 6 3 9 3 1 4 3 4 5 4 6 4 7 4 9 4 10 4 4 5 10 5 1 6 3 6 8 6 1 7 1 8 3 8 9 8 1 9 7 9 1 10 2 10 4 10 8 10
Uloha 6: Orientovany graf s vahami
Zobrazte predosly orientovany graf s oznacenim hran podla vahy spojenia. Nakreslite hrubku hran proporcialne s vahami.
s = col; % zoznam vychadzajucich vrcholov t = row; % zoznam vchadzajucich vrcholov weights = M(M>0); % najde hrany s pozitivnou vahou names = {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J'}; % oznaci mena vrcholov G = digraph(s,t,weights,names); % definuje orientovany graf G.Nodes % vypise na obrazovku zoznam hran aj s vahami G.Edges % vypise na obrazovku zoznam vrcholov plot(G,'Layout','force','EdgeLabel',G.Edges.Weight) % zobrazi orientovany graf s vahami pri kazdej hrane Widths = 5*G.Edges.Weight/max(G.Edges.Weight); % preskaluje hrubku hran p = plot(G,'NodeColor','red','EdgeColor',[0 0.6 0],'EdgeLabel',G.Edges.Weight,'LineWidth',Widths); % zobrazi hrany s definovanymi % preskalovanymi hrubkami
ans = Name ____ 'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' ans = EndNodes Weight __________ ______ 'A' 'D' 4 'A' 'F' 10 'A' 'G' 7 'A' 'H' 3 'A' 'I' 5 'A' 'J' 10 'B' 'J' 10 'C' 'D' 7 'C' 'F' 3 'C' 'H' 7 'D' 'E' 5 'D' 'J' 9 'E' 'A' 9 'E' 'D' 3 'F' 'B' 9 'F' 'C' 5 'F' 'D' 10 'G' 'D' 5 'G' 'I' 3 'H' 'F' 8 'H' 'J' 4 'I' 'B' 1 'I' 'C' 3 'I' 'D' 1 'I' 'H' 10 'J' 'D' 2 'J' 'E' 8
Uloha 7: Zmena vzhladu grafu
Vyskusajte nastavenie grafickych vlastnosti grafu: velkost vrcholov, hrubka hran, farby, atd.
p.NodeColor = [0,0,0];
p.MarkerSize = 7;
p.Marker = '<';
p.EdgeColor = [0,0,0.7];
p.XData = [0,1,0,1,0,1,0,1,0,1];
p.YData = [0,0,1,1,2,2,3,3,4,4];
Uloha 8: Text oznacenia vrcholov
Zmente velkost textu oznacenia vrcholov.
q = plot(G,'NodeColor','red','EdgeColor',[0 0.6 0],'EdgeLabel',G.Edges.Weight,'LineWidth',Widths); q = plot(G,'NodeLabel',[]); q.NodeColor = [0,0,0]; q.MarkerSize = 7; q.Marker = '<'; q.EdgeColor = [0,0,1]; q.XData = [0,1,0,1,0,1,0,1,0,1]; q.YData = [0,0,1,1,2,2,3,3,4,4]; for i=1:10 text(q.XData(i)-0.05,q.YData(i),num2str(i),'fontsize',16); end
Uloha 9: Podgraf
Vygenerujte orientovany graf s 5 vrcholmi a vygenerujte nahodne hranamy s pravdepodobnostou 1. Definujte podgraf, ktory bude obsahovat vrcholy 1,2,5 a hrany medzi nimi. Znazornite tento podgraf inou farbou v obrazku povodneho grafu.
p = 0.7; % pravdepodobnost hrany vertices = 1:20; % vrcholy n = numel(vertices); % pocet vrcholov M = rand(n,n); % nahodna matica s rozdelenim U([0,1]) M = tril(double(M<p),-1); % dolna trojuholnikova matica bez diagonaly M = M + transpose(M); % symetrizuj G = graph(M~=0); p = plot(G,'NodeColor','k','EdgeColor','k','LineWidth',1,'MarkerSize',7,'NodeLabel',[],'layout','circle'); axis square for i=1:n text(p.XData(i)+0.1,p.YData(i),num2str(i),'fontsize',16); end SN = [1 2 5 6]; % vybrane vrcholy highlight(p,SN,'NodeColor','r') % zvyrazni vybrane vrcholy podgrafu N = vertices; N(SN)=[]; % vyrobime novu maticu definujucu graf s hranami, ktore spajaju iba vybrane vrcholy M2 = M; M2(N,:)=0; M2(:,N)=0; H = graph(M2~=0); % vzniknuty podgraf H highlight(p,H,'NodeColor','r','EdgeColor','r','LineWidth',2) % zvyrazni vybrane vrcholy a hrany podgrafu