Sziasztok !
Mivel nem találtam más topicot így itt tenném fel az alábbi kérdést :
Adott egy X (adott szám)pontos gráf amiről tudjuk , hogy a fokszámainak átlaga Y(adott szám tizedesben) . A kérdés hogy hány darab 0 van a gráf ILLESZKEDÉSI mátrixában ?
U.i.: megpróbáltam a Google-t fellapozni, de ilyen feladatokra definíciókon kívül más magyarázatot , példát nem találtam.
Köszönöm a segítséget előre is !
- 451 megtekintés
Hozzászólások
Tippre, régen volt már a gráfelmélet: A fokszámok átlaga ugye a fokszámok összege osztva a pontok számával, vagyis összesen x*y/2 [minden él két pont fokszámába is belemászik, ezért a kettővel osztás] él van - vagyis jó esetben x*y páros egész szám, ha nem, akkor már itt bukott az elméletem. :) Így ugye a mátrix mérete x*(x*y/2) [pontok száma * élek száma], minden él két elemet tesz 1-essé (*), a többi nulla, vagyis (x*(x*y/2))-(2*(x*y/2)) [összes elemek száma minusz a nem-nulla elemek száma], kicsit átrendezve: y(x^2/2 - x).
Elvileg, de majd valaki jól kijavít, hogy hol néztem be.
(*): A hurokéleket passzolom (ugye a fokszámba beletartoznak, viszont csak egy nem-nulla érték lesz hozzá a mátrixban)
Szerk.: A "lábjegyzet" csillagozást furán dolgozta fel a HUP... egyébként jobban utánanézve, megoszlanak a vélemények a hurokélekkel rendelkező gráfok incidence mátrixáról, találtam olyan doksit, ahol kapásból úgy definiálják, hogy hurokélet nem tartalmazó gráf az input...
BlackY
--
"en is amikor bejovok dolgozni, nem egy pc-t [..] kapcsolok be, hanem a mainframe-et..." (sj)
- A hozzászóláshoz be kell jelentkezni