Matematika - gráfok (Egyetem)

 ( dfazekas97 | 2019. május 8., szerda - 12:16 )

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 !

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

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)