주메뉴바로가기.. 본문바로가기

MathFun

매스펀

[함께 풀고 싶은 문제] 그래프 색 전환하기 문제의 일반화

EulerD | 2019.01.12

같이 풀어볼까?

네이버밴드 구글플러스

임의의 Simple Graph G에 대해 k coloring을 부여한다.

각 color을 1, 2, ... ,k라 한다.

V(G)의 원소 v에 대해 함수 f(v)를 다음과 같이 정의한다.

v와 N(v)의 색의 값을 1  추가한다.

단, k+1 = 1

 

이때 몇번의 함수 시행으로 모든 점의 색을 같게 할 수 있음을 보여라.

댓글 4

  • 디듀우 2019.01.12 21:41:16

    Simple Graph에 대해 설명해주실 수 있나요?

    좋아요0 댓글수3
    • EulerD 2019.01.13 07:52:27

      http://mathworld.wolfram.com/SimpleGraph.html

      좋아요0
    • 디듀우 2019.01.13 10:06:39

      그래프에서 두 점을 두 번 잇거나 자기 자신과 연결되는 변이 없다는 건가요?

      좋아요0
    • EulerD 2019.01.15 07:11:13

      좋아요0