Grafy, które nie są izomorficzne

damian18833 · Post autor: **damian18833** » 19 sty 2013, o 21:06

Witam, dlaczego grafy przedstawione na rysunku nie są izomorficzne? Mają tą samą liczbę krawędzi, wierzchołków, równą liczbe wierzchołkow tego samego stopnia.

szw1710 · Post autor: **szw1710** » 19 sty 2013, o 21:27

Lewy zawiera dwa podgrafy izomorficzne z "kwadratem", prawy trzy (trapez na górze). Może to jest powód. Zastrzegam, że nie znam się na teorii grafów

qbex · Post autor: **qbex** » 28 sty 2013, o 18:46

W drugim grafie wszystkie wierzchołki stopnia 3 sąsiadują ze sobą, w pierwszym natomiast nie.

yorgin · Post autor: **yorgin** » 28 sty 2013, o 18:52

Albo jeszcze inaczej - mają różne macierze sąsiedztwa.

To zadanie pochodzi bodaj z Wilsona. Klasyka