V := {0, 1, 2, 3, 4, 5}.
E := {(0, 1), (1, 2), (2, 0), (2, 3), (2, 5), (4, 3)}.
f(v) := {v} for v in V.
g(0) = {0, 1, 2, 3, 5}.
g(1) = {0, 1, 2, 3, 5}.
g(2) = {0, 1, 2, 3, 5}.
g(3) = {3}.
g(4) = {3, 4}.
g(5) = {5}.
- dc official App
잘 관찰해보면 v에서 v'로 가는 경로가 있을 때 그리고 그럴 때에만 f(v')가 g(v)의 부분집합임을 알 수 있습니다. - dc App
경로 개념 이해하고 올게
나 질문 해도 돼? 위키백과에 유향그래프 찾아보니까 유향 그래프는 Gamma =(V,E)는 집합 V와, V의 순서쌍들로 구성된 집합 E \subset V \times V의 순서쌍이다 라는데 그럼 E는 임의의 V의 원소 두 개를 집어서 만들 수 있는 집합들 중 하나라는거지?
질문 환영이요. 네 맞아요. - dc App
유향그래프에서 E의 두 원소는 적은 순서대로 점과 점사이의 경로가 되는구나 여기까진 이해했어 근데 그럼 V->2^X가 이해가 안돼 난 그냥 대수적인 제곱 개념이라 생각했는데 먼가 경로의 갯수라고 해야하나 그런게 바뀌는 작업인거임?
2^X는 X의 부분집합들의 집합이에요 - dc App
글쿠나 f랑 g가 만들어내는 집합이 정의될 수 있게 해주는게 X랑 2^X인가보네 그럼 조건 2가 이글 첫댓에 니가 준 힌트랑 같은 의미인거같은 느낌이 드네
네 - dc App
문제에서 말하는 가장 작은 함숫값을 가지는 함수라는건 그럼 너가 준 예시에서 V,E,f는 그대로 뒀을때 너가 정의한 g보다 더 적은 원소와 부분집합들을 가진 g가 있을 수 있고 그것들 중에 가장 간소한 놈이라는건가 보네!
맞는거같네 거기다 f도 주어진다고 되어있구나 이제야봤네
제가 정의한 g 중에서 가장 간소한 놈이요 - dc App
ㅇㅇ 이해햇서
ㅊㅋㅊㅋ - dc App
니가 준 예시에선 그럼 g0=0,1 g1=1,2 g2=0,2,3,5 g3=3 g4=3,4 g5=5 이게 젤 간소한 g0일려나?
간단하게 적는다고 섞어썼네 g0 g1 얘네들 g(0)이런거고 간소한 g0가 문제가 말한 g0
아니요. g(0) = g(1) = g(2) - dc App
g(0) = g(1) = g(2)이어야 해요. - dc App
테에에에엥 문제 덜 이해했나보다 다시 보구올게
직접 점 찍고 경로 그려보니까 0120 순서로 서로 순환하는 경로던데 이거랑 g(0)=g(1)=g(2)랑 관련있는거야?
네 맞아요 - dc App
아 경로 입장에서 생각하면 0 1 2어디서 시작하든 012각각이랑 연결된 다른 점으로 언젠간 갈 수 있어서구나? 그럼 너가 정의한 g가 젤 간소한거같은데 맞지?
네 - dc App
그럼 문제에서 원하는 해답은 어디까지를 원하는건지 궁금해. f(x)가 뭔지 정해져야 실제 g(x)를 만들 수 있는거 아님? f(x)가 뭐든 간에 g(x)를 일반적으로 구해낼 수 있는 방법이 있는거고 그거를 알아내라는거야?
네 맞아요 - dc App
1. f(x)가 주어지면 V의 모든 원소를 f(x)에 대입해서 f(v)별로 뱉어낼 집합을 만들어두고, 2. E의 모든 원소에 대해 조건 2를 만족하는 임의의 집합들를 만들어낸 다음 1번에서 만든거랑 합쳐서 두 조건을 만족하는 집합을 반환하는 함수가 되게 한다 이게 내가 생각하는 방법인데 V랑 E를 전부 돌면서 만들어내니까 이것보다 더 간단한 방법이 있을거같
http://m.dcinside.com/board/github/2812
- dc App