행렬과 그래프에 관한질문입니다.

Question

행렬과 그래프에서 서로같은그래프에 관한 질문인데요.
각꼭지점에연결된 변의 개수만 맞으면 무조건 서로 같은 그래프라고 볼수있는거 맞죠?
순서에상관없이 3/3/3/3/4/ 이러고 따른그래프도 4가 1개 3이 4개이면 두그래프는 서로같은 그래프라고 보면되는거죠?

그래프와 행렬 에서 왜 항상 1행1열 2행2열이런 대각선 행렬은 항상 0이여야하나요?
제가 삼수생이여서 작년에 행렬공부할떄 경로같은거 할떄는 1번꼭지점에서 출발해서 1번꼭지점으로돌아오는 그런식의
그래프가 있다면 대각선에도 숫자가 들어갈수 있지않나요?
마찬가지로 1번꼭지점에서 2번꼭지점으로 가는 변이 두개 있을수도 있지않나요?
제가 기본서를 풍산자로 놓고 공부하는데 여기책에는 항상 행렬이 0과1로 도배되어 있어서 질문드립니다.
이책만 그런건가요 아니면 모든 행렬과 그래프는 0과1로만 원소가 구성되어있나요?

dsfadsfad · Accepted Answer

1.   예 맞는 말입니다. 단 조건이 있습니다. 두 그래프의 꼭지점의 이름이 정해져있지 않아아해요.
      예를들어, A그래프에서 꼭지점 a에 연결된 변의개수가 3개고 B그래프에서 꼭지점 a에 연결된 변의 개수가 2개면 두 그래프는 다른겁니다.
     그런데, 그래프에서 문제로 나올때 꼭지점의 이름을 부여 하지않는 경우가 많기 때문에 꼭지점의 개수와 각꼭지점에 연결된 변의개수만 맞으면 무조건 서로 같은 그래프라고 볼수 있습니다.

    2.새로 개정된 교과서에 이렇게 나옵니다. "한 꼭지점에서 다시 자기 꼭지점으로 오는 경우는 생각하지않는다.(그러니까 님이 말하신 1번꼭지점에서 출발해서 1번꼭지점으로 돌아오는 경우는 생각하지않겠다는겁니다.)" 
      또한,  "한꼭지점에서 다른꼭지점에 연결된 변의수는 최대 1개만 있다고 생각하고 2개이상 있는경우는 생각하지 않는다.(그러니까 님이 말하신 1번꼭지점에서 2번꼭지점으로 가는 변의 개수가 2개인 경우를 생각하지않겠다는겁니다.)"라고 나옵니다.
    그러므로 행렬에서 대각에 있는 성분은 반드시 모두 0이고 그래프를 행렬로 표현한 인접행렬의 모든 원소는 필연적으로 0과 1로만 구성될 수밖에없습니다.
   (현행교과서에서 최대한 간단히 생각하기 위해 이렇게 약속한겁니다. 자기자신으로 돌아올 수 있고 다른곳으로 갈수있는 길이 2개이상이면 생각하기 복잡해지면 곤란하니까요.)

가시꽃 · Answer

차수(각 꼭지점에 연결된 변의 개수)가 같다고 해서 항상 같은 그래프라고 할 수 없습니다. 차수가 같더라도 그래프 개형이 다를 수 있습니다. 가장 확실한 방법은 ( 비효율적이지만 증명같은 것을 할 때 쓰여요 ) 그래프 마다 꼭지점의 집합과 변의 집합을 모두 쓴 다음 각각 비교하는 방법이라고 생각합니다. 물론 저의 생각이니 다른 더 좋은 방법이 있을지도 ㅠㅠ...

행렬과 그래프에 관한질문입니다.

최근 게시글 · 더보기

오르비 캐스트