A teljes gráf
Definíció
Olyan egyszerű gráf, amelyben minden egyes csúcs az összes többivel össze van kötve. Az csúcsú teljes gráf jele: .
Teljes gráfnak nevezünk egy n elemű halmazt (pontok halmaza) különböző elemeiből képzett párjaival (élek halmaza). A pontokat általában { 1 , 2 , . , n } = [ n ] jelöli, az éleket i j és a teljes gráfra a K n jelölés szokásos.
Teljes gráf, Kn: olyan (egyszerű) gráf, amelyben minden pontpár össze van kötve éllel
n pontú teljes gráf élszáma
üres gráf: olyan gráf, amelyben nincs él (a teljes gráf komplementere)
Végtelen gráf: olyan gráf, amelynek végtelen sok csúcsa van ...
Az n csúcsú teljes gráf (jelölése ) az az n csúcsú gráf, melyben bármely két csúcs szomszédos. A példa gráf nem teljes gráf. éleinek száma az összes lehetséges csúcspárok száma, azaz .
Feladat: Egy teljes gráf csúcshalmaza legyen {1,2,3,...,n}. Az ij él súlya legyen i+j. Határozzuk meg a legnagyobb súlyú feszítőfát.
a) Átlagosan hány lépésben jutunk el az n pontú teljes gráf egyik csúcsából egy kijelölt másik csúcsba? (A bolyongás csúcstól-csúcsig történik, az éleket minden csúcsban véletlenszerűen választva.) ...
Mit nevezünk gráfnak? Mi az n pont teljes gráf? Mi az egyszerű gráf? Mi az összefüggő gráf?
 See also: Gráf, Bizonyítás, Él, Halmaz, Definíció
  
|
RSS
