[일반] 그래프이론 질문

[오렌(snrnrp483810)]

G3의 각 점의 degree와 G4의 각 점의 degree가 같으면

서로 isomorphic이라고 주장할수 있을까요?

G3은 A부터 4 4 5 4 4 5

G4는 1부터 4 4 5 5 4 4

둘다 5 2개 4 4개니까맞을꺼같은데...틀리나요?

[익명(14.33)]

안됨

[오렌(snrnrp483810)]

혹시 역은 참인가요? 맞을거같은데..

[Rafle(probaroque)]

역은 당연하잖아;;

[오렌(snrnrp483810)]

아..그럼두 그래프가 isomorphic인지는 노가다로 확인해봐야하나요?

[adf(203.229)]

반례: 6각형에서 두 꼭지점 이어서 사각형 두개로 나눠진거랑 삼각형+5각형으로 나눠진거

[오렌(snrnrp483810)]

ㄴ 되지않나요?

[adf(203.229)]

isomorphic 하려면 v1이랑 v2가 인접하면 f(v1)이랑 f(v2)도 인접해야되잖음. 그럼 전자는 1번꼭지점이랑 3번꼭지점을 이었다고했을때 1-2-3-1 이렇게 이어지는데 후자는 1번꼭지점이랑 4번꼭지점을 이엇으면 1'-2'-3'-4'-1' 이렇게 되거나, 1'-6'-5'-4'-1' 이렇게 이어지잖음

[adf(203.229)]

그럼 1이랑 1'이랑 대응시켰으면 2를 2'나 6'로 대응시켜야되고, 이렇게 했을때 하다보면 1이랑 1'랑 대응안되는 모순이발생됨

[adf(203.229)]

아 전자/후자 바꿔썼음...

[오렌(snrnrp483810)]

하....졸루어렵다

[Rafle(probaroque)]

이 경우는 둘 다 완전그래프에서 안 겹치는 두 변 뺀거니까 isomorphic한데 일반적으로 degree만으로는 안 된다. 예를 들어 12개 점에서 전부 2면 삼각형 네 개인지 사각형 세 개인지 구별이 안 되거든