토론:그래프 (그래프 이론)

그래프에 올려진 그림으로는 그래프의 정의를 바르게 설명할 수 없습니다.

편집하려고했는데 그림기여가 막혔네요. 편집허가해주십시오. Linear Function (토론) 2014년 2월 14일 (금) 22:30 (KST)

영어 위키백과의 한 서술에 대해서

In model theory, a graph is just a structure. But in that case, there is no limitation on the number of edges: it can be any cardinal number, see continuous graph.

모형 이론에서도, 그래프는 그냥 아무런 구조가 아니라 그래프 공리를 만족시키는 구조입니다. 그와 별개로, 구조를 그래프의 일반화로 여기는 것 자체도 부적절합니다. 그래프는 구조의 한 종류일 뿐입니다. 우리가 자연수를 소수의 일반화라고 하지는 않죠. 참고를 위해 적어 둡니다. 慈居 (토론) 2025년 2월 9일 (일) 15:09 (KST)

유향 그래프와 다중 그래프

유향 그래프나 다중 그래프는 이미 별도의 문서에서 다뤄지고 있습니다. 이 글은 (무향 단순) 그래프에 집중해야 합니다. 가장 흔한 의미만 별도의 문서가 없는 건 이치에 맞지 않습니다. 환 (수학)과 유사환도 같은 방식을 취합니다. 환은 1을 가지는지 여부에 따른 두 의미를 가지지만 (그 밖에도 결합 법칙 요구 여부 등 동음이의가 존재), 환 (수학)은 1을 갖춘 환을 다루고 유사환은 1을 갖출 필요가 없는 환을 다룹니다. 慈居 (토론) 2025년 2월 10일 (월) 09:01 (KST)

유향 그래프와 다중 그래프는 무향 단순 그래프에 대한 서술이 추가적으로 있을 때 더 매끄럽게 정의가 연결되는 것으로 보입니다. (무향 단순) 그래프에 집중하는 것은 좋아 보입니다만, 기존 문서의 서술 방식은 그래프의 추상적인 구조에 집중하고 있어 유향 그래프와 다중 그래프와의 연관성이 떨어져 보이기에 정의 문단에 이를 서술했습니다. 정의 문단에서 유향 그래프와 다중 그래프를 특별히 빼야 할 이유도 부족한 것 같습니다. 별도의 문서에서 더 서술하는 것에는 이견이 없습니다. Matpie (토론) 2025년 2월 11일 (화) 00:06 (KST)

유향·다중 그래프를 정의에서 서술하면, 성질이나 예에도 유향·다중 그래프 관련 내용을 추가해야 하는가 하는 의문이 작용할 수 있습니다. 말씀드린 대로, 이 문서에서는 (무향 단순) 그래프에 집중해야 하며, 그러려면 그 밖의 내용은 뒤에서 간단히 소개만 하는 것이 맞습니다. 慈居 (토론) 2025년 2월 11일 (화) 08:37 (KST)

그렇다면 정의에서 유향•다중 그래프를 뺄 경우 무향 단순 그래프와의 혼용 및 혼동을 막기 위해 본 문서의 정의가 무향 단순그래프만을 의미함을 명시하는 것이 필요할 것 같습니다. 문서 윗부분에서(맨 처음 또는 정의 문단) 이를 명백히 서술하고 유향•무향그래프에 대한 서술을 정의 문단이 아닌 관련 개념 문단에 넣는 것까지는 받아들일 수 있습니다. Matpie (토론) 2025년 2월 11일 (화) 18:03 (KST)

대체적으로 동의합니다. 다만

이 글에서 그래프는 무향 단순 그래프를 뜻한다.

는 식으로 하지 않고

그래프는 유향 그래프와의 구분을 위해 무향 그래프라고 불리기도 하며, 다중 그래프와의 구분을 위해 단순 그래프라고 불리기도 한다.

는 기존 태도를 유지했으면 좋겠습니다. 慈居 (토론) 2025년 2월 11일 (화) 20:23 (KST)

정정합니다. 다른 문단(가령 '관련 구조')의 내용이므로, 정의 문단에서 중복해서 서술하는 대신, 서론에서 요약 서술되어야 합니다. 慈居 (토론) 2025년 2월 14일 (금) 10:49 (KST)

동의합니다. Matpie (토론) 2025년 2월 14일 (금) 13:01 (KST)

일반화?

그래프 이론에서 주로 다루는 이산적인 구조로서의 그래프를 주 내용으로 삼고 있지 않기 때문에

사실이 아닙니다. "범주론적 성질"과 "위상수학적 성질"에서 다루는 성질들은 모두 그래프의 성질이며, "논리학적 성질"에서 다루는 성질들은 그래프 및 그래프의 1차 이론의 성질들입니다.

기존 글 구조는 이산적인 구조로서의 그래프에 대한 내용을 충분히 부각하기 어렵습니다.

기초적 성질을 다루려면 성질에 다른 문단을 추가하거나, 성질 문단의 서두 부분을 이용하면 됩니다. 이미 다음과 같은 기초적 성질이 하나 설명되어 있습니다.

어떤 그래프에 있는 모든 꼭짓점 차수의 합은 이 그래프가 가진 변의 수의 두 배가 된다. 따라서, 꼭짓점 차수의 합은 짝수가 되면, 차수가 홀수인 꼭짓점의 수도 짝수가 된다는 성질을 가진다.

慈居 (토론) 2025년 2월 10일 (월) 09:19 (KST)

기존 문서가 이산적인 구조로서의 그래프를 주 내용으로 삼고 있지 않는다는, 즉 그래프 이론의 주요 개념으로서 다루지 않는다는 점이 어떤 부분에서 사실이 아니라고 말하시는 건지 사실 잘 납득이 가지 않습니다. 성질 문단에 있는 내용은 말씀하신 바대로 그래프의 성질이 맞는데, 제가 말씀드린 바는 이 성질들이 통상 이산 수학의 하위 분야로서의 그래프 이론에서 다루는 내용이 아니라는 것입니다. 문서의 제목인 그래프 (그래프 이론)에서도 본 문서가 그래프 이론의 내용을 중점적으로 다룰 것임을 명시하고 있기도 합니다.

기초적 성질을 문단에 추가해서 작성하는 것도 하나의 방법이 될 수 있고, 이렇게 해도 큰 문제는 없을 수 있어 보입니다. 다만, 모형 이론이나 범주론, 위상수학과 논리학적 성질을 다루는 내용이 문서 윗부분에 있는 경우(즉 '예', '관련 개념'보다 위에 오는 경우) 이 분야를 잘 알지 못하는 독자에게는 가독성이 상당히 떨어진다는 단점이 있습니다. 그리고 본 문서는 그래프 이론의 가장 중심이자 기초 개념이므로 이를 모르는 독자도 최대한 매끄럽게 읽을 수 있도록 설명하는 것이 바람직해 보입니다. 기존 구조는 이 관점에서 완성도가 매우 떨어집니다. 따라서 그래프 이론 분야 외에서 다루는 내용은 가장 마지막 문단으로 빼는 것이 옳아 보이며, 이는 위키백과뿐만 아니라 수학 개념을 서술하는 문서의 일반적인 서술 방식입니다. '일반화'라는 단어가 마음에 들지 않는다면 '확장'이나 '다른 분야와의 연관성' 등의 단어를 쓰는 것도 괜찮아 보입니다. Matpie (토론) 2025년 2월 11일 (화) 00:17 (KST)

그래프의 주요 개념 중 하나인 경로나 연결성, 부합, 평면 그래프, 그래프 색칠, 작용(graph operation) 등도 기존 구조로는 서술하기 어렵고 모두 성질이나 관련 개념 문단에 넣을 수도 없는 노릇입니다. 적어도 정의 문단에서 모형 이론이나 범주론 관점에서의 내용은 후술하는 것이 바람직해 보이며, 성질 문단을 그대로 둔다고 하더라도 예시나 관련 개념 문단을 위로 올리는 것이 나아 보입니다. Matpie (토론) 2025년 2월 11일 (화) 00:35 (KST)

그래프 이론은 초등 그래프 이론에 국한되지 않습니다. 범주론적 그래프 이론, 위상수학적 그래프 이론도 그래프 이론의 분야입니다. 그래프의 어떤 성질은 그래프 이론의 내용이 아니라는 관점은, 그래프 이론의 정의에 부합하지 않고, 서로 다른 수학 분야가 융합되어 가는, 새롭지 않은 추세에도 부합하지 않습니다.

"기초적 성질" 문단을 추가할 수도 있고, 말씀하신 "연결성", "부합", "평면성", "색칠" 등 문단을 추가해서 다룰 수도 있습니다. 예 문단의 내용은 정의나 성질 문단 내용을 언급해야 하기 때문에 위로 올리기 부적절합니다. 예를 "추가 예"로 바꾸고 성질 위에 예를 만드는 정도는 받아들일 수 잇습니다. 慈居 (토론) 2025년 2월 11일 (화) 08:35 (KST)

범주론적•위상수학적 그래프 이론이 그래프 이론의 하위 분야라 하더라도 초등 그래프 이론의 내용을 중점적으로 다루어야 한다고 생각합니다. 말씀드렸듯이 독자의 가독성을 위해서입니다. 대부분의 독자가 이해하기 어려울 것으로 예상되는 성질 문단의 내용(그리고 정의 문단에서 모형 이론과 범주론, 위상수학적 관점에서 서술한 내용)들은 후술하는 것이 바람직해 보입니다. 서술 방면에서 수학적인 구조적 아름다움은 어느 정도 포기하더라도 초등 그래프 이론의 내용이 앞서 나오는 것이 학계에 종사하는 연구자만이 아닌 모든 독자를 대상으로 하는 위키백과의 취지에 맞다고 생각합니다. 혹여 초등 그래프이론보다 범주론적•위상수학적 그래프 이론이 더 활발하게 연구되고 있는 분야라면 모르겠지만, 적어도 앞서 언급한 문단에 있는 내용들은 가장 마지막에 서술해야 한다는 의견 드립니다. 예 문단과 관련 개념 문단의 내용(제가 마지막에 편집했던 문서판 기준으로)이 정의 문단보다는 뒤에 나와야겠지만 성질 문단보다는 앞서 있는다 해도 읽는데 별다른 지장이 없을 뿐더러, 오히려 성질 문단이 앞서 나오는 것이 배경지식이 별로 없는 독자가 그래프의 예를 이해하기 어렵게 할 것으로 예상되기 때문입니다. 만약 이를 받아들이지 않는다고 하신다면, 초등 그래프 이론의 내용을 모두 '기초적 ~'로 서술해 문서 앞부분에 두고 모형 이론, 범주론, 위상수학적 내용을 모두 후술하는 것을 제안드리는 바입니다. Matpie (토론) 2025년 2월 11일 (화) 18:25 (KST)

모든 독자를 고려하고자 하는 과정에서 높은 수준의 수학을 구사하는 독자, 또는 그렇지 않더라도 어려운 주제에 관심을 보이는 독자들을 '주변화'하는 결과가 빚어져서는 안 되겠습니다. 그런 의미에서 초등적이지 않은 측면들을 '잘 안 보이는 구석 한 켠'에 위치시키는 방식은 받아들이기 어렵습니다. 언급하신 범주·논리·위상적 성질들이 특별히 더 어려운 성질들도 아니구요. (깊은 결과들은 오히려 저희가 "기초적 성질"로 일컫고 있는 쪽에 더 많습니다.) 마지막에 제안하신 바는 성질 문단에서 범주·위상·논리적 성질들을 마지막에 위치시키자는 것으로 이해됩니다. 제가 잘 이해했다면, 이는 제 생각과 일치하는 바입니다. 慈居 (토론) 2025년 2월 11일 (화) 20:15 (KST)

(추가) 별도의 문서가 존재하는 기초적인 성질들은 이 문서에서는 요약적으로 다뤄져야 하겠습니다. 慈居 (토론) 2025년 2월 11일 (화) 20:25 (KST)

범주•논리•위상적 성질은 기초적 성질에 비해 기본적으로 알고 있어야 하는 선행지식이 많이 필요한 것은 사실이며(초등 그래프 이론은 고등학생 수준만 되어도 이해할 수 있기 때문), 따라서 이를 이해할 수 있는 독자는 관련 개념들에 익숙할 것으로 예상되므로 내용이 잘 안 보이는 구석 한 켠에 있다 하더라도(그렇다고 생각하지도 않기는 합니다만) 잘 모르는 독자에 비해 상대적으로 쉽게 찾을 수 있어 큰 문제가 되지 않을 것이라는 게 제 생각입니다. 특히 본 문서는 중요도와 범용성이 큰 개념이기에 더욱 일반 독자를 대상으로 해야 합니다. 이런 서술이 꼭 높은 수준의 수학을 구사하는 독자를 '주변화'한다고 보기도 조금 어렵지 않나 싶고요.

아무튼 합의안으로 현재의 성질 문단 내용을 후술하는 것에는 동의하시는 것 같은데, 구체적으로 성질 문단이 어느 위치에 있어야 할지, 즉 예와 관련 개념 문단 등을 어떻게 해야할지에 대해서도 의견 주시면 감사하겠습니다. 제가 제안드리는 바는 현재 문서 내용 기준으로 정의/관련 개념/예/성질/응용 순서입니다.

또한 (慈居 님이 마지막으로 편집한 문서 기준으로) 정의 문단의 차수 이후부터의 하위 문단 내용들을 관련 개념 문단으로 빼고, 유향•다중 그래프 내용은 관련 개념 문단에 서술(또는 관련 구조 문단을 넣어 예 문단 이후에 위치)하는 것을 제안드립니다. Matpie (토론) 2025년 2월 14일 (금) 00:10 (KST)

성질 '문단 내'에서 위치를 조정한 것으로 이미 충분한 배려를 하고 있습니다. 어려운 내용을 모조리 뒤에 놓는 것은 지나치게 기계적입니다. 시중 교재에서도 어려운 내용을 모두 뒤로 놓는 대신, 적절한 위치에 놓고 별표를 매기는 등 방법을 사용합니다. 모두를 배려하는 대안이 있음에도 소수를 불편하게 만드는 방법을 선택하는 것은 소수에 대한 주변화에 해당합니다.

저는 차수나 부분 그래프 등 내용도 정의 문단에 있어야 한다고 생각합니다. 제가 선호하는 방안은 이렇습니다.

== 정의 ==
=== 꼭짓점과 변 ===
=== 차수 ===
=== 동형과 부분 그래프 ===
== 예 ==
== 성질 ==
== 추가 예 ==
== 관련 구조 ==

慈居 (토론) 2025년 2월 14일 (금) 10:45 (KST)

어려운 내용을 앞부분에 위치시켜 가독성을 떨어뜨리는 것이 어째서 모두를 배려하는 대안이라고 생각하시는지 잘 납득이 가지 않습니다. 지금 제안해주신 방안은 제가 느끼기에 오히려 다수를 불편하게 만드는 방안인 것 같습니다. 예와 추가 예를 왜, 어떻게 따로 분리해야 하는지도 의문이 있습니다.

정의 문단에 관련 내용을 서술하는 것은 받아들일 수 있습니다. 다만 이 경우 제가 마지막에 편집했던 문서 기준으로 완전 그래프•여 그래프, 경로, 연결 그래프와 유한 그래프 등에 대한 내용과 이후에 추가될 수 있는 내용도 마찬가지로 그래야 하는지에 대해 의견 주시면 감사하겠습니다. 제 생각에는 '유형' 또는 '관련 개념'으로 정의 아래 문단에 서술하는 것이 좋을 것 같습니다.(부합, 평면성, 색칠 등에 대한 개념도 이 문단에서 다룰 수 있어 보입니다.) Matpie (토론) 2025년 2월 14일 (금) 13:00 (KST)

어려운 내용을 앞에 배치시킨 게 아닙니다. 기존 기여분에서도 차수 관련 성질은 범주·위상·논리적 성질 앞에 배치되어 있었습니다. 다만 성질이기 때문에 같이 묶인 것이지요. 목차가 있고, 문단 제목이 난이도에 대한 어느 정도 힌트를 주고 있기 때문에 가독성에 대한 영향은 제한적입니다. 범주·위상·논리적 성질 문단에도 일부 기본적인 성질들(이를테면 쌍대곱과 곱의 구성)이 서술되어 있는데, 뭉뚱그려서 뒤에 놓아야 한다고 제안하셨습니다. 그리고 범주·위상·논리적 측면이 초등적 측면의 여집합이라고 가정하신 것처럼 느껴집니다. 저로서는 깊은 고려가 들어있지 않은 제안이라고 생각할 수밖에 없습니다. (저를 포함한) 소수를 불편하게 만드는 것은 결과적인 것이구요.

완전 그래프나 연결 그래프는 '종류' 문단 아래 놓는 것이 좋아 보입니다. (유한 그래프나 국소 유한 그래프도 여기로 옯겨야 합니다.) '종류' 문단은 '성질' 문단 아래 배치되어야 합니다. 특수한 종류의 그래프의 성질은 일반적인 그래프의 성질을 확립하고 난 다음 논의되어야 합니다.

'예'와 '추가 예'는 같은 예시들을 다루되, 각 문단에서 앞서 언급된 개념들을 집중해서 다뤘으면 합니다. 가령 '예'에서는 인접 여부나 차수, 부분 그래프 등을 다루고, '추가 예'에서는 '성질'이나 '종류'에 언급된 개념들을 다루는 것을 생각할 수 있습니다. 이는 제가 원하는 바와는 많이 다르고, 타협을 위해 제안한 방안입니다. 慈居 (토론) 2025년 2월 14일 (금) 13:53 (KST)

구조적으로는 성질 문단이 예시나 종류 등의 문단 앞에 오는 것이 자연스럽겠지만, 결과적으로는 초등적인 측면을 모르고서는 읽기 어려운 순서가 됩니다. 그래프 이론의 초등적인 측면이 다른 측면보다 주 대상으로서 많이 다뤄지기 때문에(제가 알기로는 그렇습니다) 이를 부각시켜야 한다는 관점이기도 하고요.

독자가 성질 문단의 내용을 이해할 수 있는 수준이라면 앞 문단에 종류나 예의 문단을 배치시켜놓는다고 하더라도 이미 충분히 알고 있거나 쉽게 이해할 가능성이 높습니다. 따라서 성질 문단을 뒤에 배치시켜 놓는다고 하더라도, 구조적인 아름다움은 조금 해칠 수 있을지언정 실제로 독자가 전반적인 그래프의 구조적 특성을 이해하는 데에 있어 큰 영향은 없을 것으로 보입니다. 오히려 그래프가 무엇인지 생소한 독자가 예시보다 범주론적 성질을 먼저 보고 이해하려 한다면 더 혼란스럽겠죠. 문단 제목에서 얻을 수 있는 난이도에 대한 힌트도 개념에 익숙하지 않은 독자들이 상대적으로 더 알아채기 어려울 것입니다.

종류 문단이 꼭 성질 문단 앞에 와야 하는지에 대한 의문도 있습니다. 일반적인 성질을 이해하기 어려운 경우(그리고 지금이 그 경우라고 생각합니다) 이해하기 쉬운 특수한 경우에 대해서 먼저 서술하는 방식을 취하는 경우도 많고, 현 문서에서는 이렇게 하는 것이 더 적절해 보이기 때문입니다.

한편 종류 문단에 들어가기는 어려워 보이는 부합, 색칠, 평면성 등에 대한 내용에 대한 분류도 필요할 것 같습니다. 종류 문단을 만든다면 관련 개념 정도의 문단이 적절해 보입니다.

추가 예를 다루는 것에 이견은 없습니다만, 적절한 내용을 추가하는 노력을 조금 요할 것 같습니다. Matpie (토론) 2025년 2월 18일 (화) 01:16 (KST)

자연스러운 글의 흐름을 유지하고 각자 관심 있는 부분을 골라 읽도록 하는 것이 합리적이라고 생각합니다. 정 순서가 마음에 들지 않으시면 "초습자는 건너뛰어도 좋다"는 식의 설명을 추가하는 것도 고려할 수 있으나, 이는 여러 모로 사족입니다.

이와 별개로, '성질' 문단에서 유한 그래프를 언급하고 있으므로 '종류'를 '성질' 위에 놓는 것에는 이의가 없습니다. 현재 '예' 문단은 그래프의 다양한 종류를 나열합니다. 이를 '종류'로 옮기고 좀 더 구체적인 예를 들어야 합니다. '추가 예' 문단의 경우, 가볍게 예를 드는 것에 그치지 않고, 예를 체계적으로 정리해야 합니다. 성질 앞 '예' 문단에는 우선 Matpie님께서 '정의'에 추가하셨던 예를 옮겨 놓았으면 합니다. 정의에 예를 직접 곁들이는 것은 선호하지 않습니다.

부합이나 색칠은 별도의 문단에서 다루되 문단 이름은 '연산'으로 했으면 합니다. 이 경우 그래프 값 연산과 비 그래프 값 연산을 아울러 다뤄야 하고, '차수'나 '부분 그래프', 범주론적 성질 문단의 '분리합집합'과 '텐서곱' 등을 여기로 옮겨야 합니다. 평면성은 '종류'에서 다뤄야 합니다. 慈居 (토론) 2025년 2월 18일 (화) 12:57 (KST)

알겠습니다. 그렇다면 지금 말씀하신 대로 편집해도 좋을 것 같습니다. 어느 정도 윤곽을 잡으시면 내용을 추가해 보는 쪽으로 하겠습니다.

본 문서에 열정적으로 기여해 주셔서 감사드립니다. Matpie (토론) 2025년 2월 18일 (화) 17:24 (KST)