Izomorfizmus problémák

Definíció: Gráfok, egyszerû gráfok izomorfizmusa. G=(V,E) és H=(U,F) egyszerû gráfok akkor és csak akkor izomorfak, ha van olyan f bijekció V és U között, amelyre két pont akkor és csak akkor szomszédos G-ben, ha képeik szomszédosak H-ban.

Feladat: A következõ gráfok közül melyek izomorfak?
 

Feladat: A következõ gráfok közül melyek izomorfak?
 

Feladat: A következõ gráfok közül melyek izomorfak?
 

Feladat: A következõ gráfok közül melyek izomorfak?
 

Feladat: A következõ gráfok közül melyek izomorfak?
 

Feladat: A következõ gráfok közül melyek izomorfak?
 

Otthoni munkára javaslat: Írjuk fel a 3,4 illetve 5 pontú egyszerû gráfok izomorfiatípusait, azaz adjunk egy 3,4 (vagy 5) pontú gráfok olyan listáját, hogy egyik se legyen izomorf, de bármely 4 (vagy 5) pontú egyszerû gráf izomorf legyen listánk egyik elemével.

A válasz.

Feladat:

• Rajzoljuk fel a következõ G egyszerû gráfot: G csúcsai az {1,2,3,4,5} halmaz kételemû részhalmazai. Két különbözõ csúcsot akkor és csak akkor kössünk össze, ha a halmazok metszik egymást.
• Rajzoljuk fel a következõ H egyszerû gráfot: G csúcsai az {1,2,3,4,5} halmaz háromelemû részhalmazai. Két különbözõ csúcsot akkor és csak akkor kössünk össze, ha a két jalmaznak pontosan két közös eleme van.
• G és H izomorf-e?