32.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 51: Riadok 51:
 
=== Domáca úloha ===
 
=== Domáca úloha ===
  
1. naprogramovať podprogram, ktorý do grafu pridá pridá novú hranu tak, že sa vďaka tomu zníži počet komponentov:
+
1. naprogramovať podprogram, ktorý do grafu pridá novú hranu tak, že sa vďaka tomu zníži počet komponentov:
 
  function TGraf.PridajHranu: Boolean;
 
  function TGraf.PridajHranu: Boolean;
 
* vráti False, ak sa už hrana pridať nedala (graf bol už súvislý)
 
* vráti False, ak sa už hrana pridať nedala (graf bol už súvislý)

Verzia zo dňa a času 07:06, 12. apríl 2013

32. Cvičenie


< 32.Prednáška | riešené úlohy


Rozcvička

1. napíšte funkciu, ktorá pre neorientovaný graf:

type
  TGraf = class
    G: array [1..N,1..N] of Boolean;
  end;
 
function TGraf.PocetIzolovanych: Integer;
  • zistí počet izolovaných vrcholov

2. napíšte funkciu, ktorá pre graf:

type
  TGraf = class
    G: array [1..N,1..N] of Boolean;   // alebo G: array of set of Byte;
  end;
 
function TGraf.JeOrientovany: Boolean;
  • zistí, či je graf orientovaný


Cvičenie

pre rôzne grafy (okolo 12 vrcholov, alebo labyrint v štvorcovej sieti)

  • najprv ručne: do hĺbky, do šírky, vzdialenosť/cestu medzi dvoma vrcholmi
  • potom zapisovať algoritmy pre:
    • stupeň vrchola
    • vrchol s najmenším/najväčším stupňom
    • veľkosť komponentu, ktorý obsahuje vrchol V
    • počet komponentov
    • najväčší komponent
    • do šírky bez Queue ale pomocou pomocného dynamického poľa


Domáca úloha

1. naprogramovať podprogram, ktorý do grafu pridá novú hranu tak, že sa vďaka tomu zníži počet komponentov:

function TGraf.PridajHranu: Boolean;
  • vráti False, ak sa už hrana pridať nedala (graf bol už súvislý)