11. gyak

1. Spektrálklaszterezzünk! Minimális (normalizált) vágások, stb.
A gráfunk a következő élek által adott. E={(1,2), (2,3), (2,4), (3,4), (3,5), (4,6), (5,6), (5,7), (5,8), (6,7), (7,8)}
Az előző órai Zachary-gráfra (http://www.cise.ufl.edu/research/sparse/matrices/Newman/index.html) is hajtsuk végre a spektrálklaszterezést.

2. Hajtsuk végre a Grivan-Newman algortimust az alábbi élek által meghatározott gráfon. E={(A,B), (A,C), (B,C), (B,D), (D,E), (D,F), (D,G), (E,F), (F,G)}

3. Mekkora lesz a klaszterezettségi együtthatója
a) egy d átlagos fokszámmal rendelkező páros gráfnak?
b) annak a gráfnak, amelyben található (i,j) élek mindegyikére teljesül, hogy 1<=|(i-j) mod |V||<=2?

4. Mekkora K_{st} jelenlétére számíthatunk abban a páros gráfban, amelyben 2*1000 csúcs található, illetve a csúcsok átlagos fokszáma 100?
s=5 esetében milyen tartományban mozoghat t?