Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

AS Matlab - Solutions

Algoritmy na sietach 2021, online

Algoritmy na sietach 2021, online

Contents

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