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
