문제풀다 궁금한게 있습니다. nolza 노드개수가 짝수개인 그래프에서 연결되있는 것 끼리 모든 노드를 2개씩 짝지을 수 있는지 없는지를 판단하려 할때 빠른 시간에 판단할 수 있는 방법이 있는지 궁금합니다. 전체 노드개수는 약 50개 정도입니다.. 또, 위에 문제를 생각하다가 궁금한게 생겼는데 위문제에서 만약에 모든 노드의 차수가 1보다 크다면 무조건 모든 노드를 2개씩 짝지을 수 있을까요? (이 때 자신을 향하는 간선은 없고 노드 a에서 노드 b가 연결되어있다면 이 사이에 간선은 1개) 반례를 잘 못찾겠습니다. 새해복 많이받으세용 11년 전
5개의 댓글이 있습니다. JongMan 새해 복 많이 받으세요. 이 문제를 일반적인 그래프에서의 매칭 문제라고 하는데 이 알고리즘을 쓰시면 푸실 수 있습니다. 모든 차수가 2 이상일 때 모든 정점을 짝지을 수 있느냐는 질문은 좀 어려운데 저도 잘 모르겠군요. 아랫분이 잘 대답해 주시지 않을까... 11년 전 link A.I 반례를 하나 만들어보았습니다.bipirtite graph인데, 한 셋에는 노드 2개, 다른 쪽은 노드 4개를 배치합니다. 그리고 서로 다른 셋에 있는 노드끼리는 서로 연결을 하게 되면 모든 노드들의 차수는 2이상이지만 최대 2개의 matching만이 가능합니다. 11년 전 link JongMan 역시 아랫분에 대한 저의 기대는 틀리지 않았군요! 11년 전 link nolza ㅇ우와 정말 딱맞는 알고리즘이네요. 새롭게 배우고 갑니다 ㅎㅎㅎ 알려주셔서 정말 정말 감사합니다 11년 전 link nolza 이렇게 쉽게 반례를 찾으시다니 정말 감사합니다 ㅎㅎㅎ 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
nolza
노드개수가 짝수개인 그래프에서 연결되있는 것 끼리 모든 노드를 2개씩 짝지을 수 있는지 없는지를 판단하려 할때 빠른 시간에 판단할 수 있는 방법이 있는지 궁금합니다. 전체 노드개수는 약 50개 정도입니다..
또, 위에 문제를 생각하다가 궁금한게 생겼는데 위문제에서 만약에 모든 노드의 차수가 1보다 크다면 무조건 모든 노드를 2개씩 짝지을 수 있을까요? (이 때 자신을 향하는 간선은 없고 노드 a에서 노드 b가 연결되어있다면 이 사이에 간선은 1개) 반례를 잘 못찾겠습니다.
새해복 많이받으세용
11년 전