부울연산부울대수(Boolean Algebra) / 논리대수(Logic Algebra): 0 또는 1을 입력 받아 0 또는 1을 출력하는 회로의 논리 계산을 형식화한 것부울값(Boolean Value): 디지털 신호, 0 또는 1부울변수(Boolean Variable): 부울값 0 또는 1을 받는 변수부울함수(Boolean Function): n개의 부울변수와 부울 연산자로 구성되는 식부울보수(Boolean Complement): 부울변수의 값을 반전시키는 단항연산자부울합(Boolean Addition): 부울변수의 값을 더하는 이항 연산자로 부울변수의 값 중 하나만이라도 1이면 그 결과가 1부울곱(Boolean Multiplication): 부울변수의 값을 곱하는 이항 연산자로 부울변수의 값 중 하나만이..
Study/이산수학
생성트리Spanning Tree, 신장트리그래프의 모든 노드를 포함하는 트리최소생성트리: 가중 그래프에 대하여 연결선의 가중치의 합을 최소로 하는 생성트리네트워크나 도로망 설계 시 비용을 최소로 하거나 효율성을 최대로 하는 경로를 고려할 때 유용최소생성트리를 구하는 알고리즘: 프림 알고리즘, 크루스칼 알고리즘프림 알고리즘Prim Algorithm주어진 가중치 그래프 G에서 최소신장트리를 프림 알고리즘으로 구하는 규칙그래프에서 임의의 노드 하나를 선택선택된(연결된) 노드들과 연결된 모든 변들 중 가중치가 가장 작은 변을 선택가중치가 같은 변은 임의로 하나를 선택순환이 형성되는 경우는 그 변은 선택하지 않음그래프 G에 포함된 모든 꼭짓점의 수가 n개일 때, n-1개의 변이 연결될 때까지 2~4의 과정을 반복..
트리루트라는 특별한 노드를 갖고 그래프를 구성하는 꼭짓점 u, v 간에 u에서 v로 가는 단순경로가 존재하는 비순환의 연결 그래프나무의 가지가 뿌리에서 뻗어나가듯이 트리는 루트를 중심으로 하나 이상의 꼭짓점(노드)들이 비선형이면서 비순환적인 경로로 연결되어 있는 형태노드: 트리인 그래프를 구성하는 꼭짓점루트: 트리인 그래프의 가장 높은 곳에 위치하는 시작 노드서브 트리: 트리인 그래프의 임의의 한 노드를 루트로 하는 트리차수: 트리인 그래프의 임의의 한 노드에 포함된 자식 노드의 개수레벨: 트리인 그래프의 루트 노드를 레벨 0으로 시작하여 자식 노드로 한 단계씩 내려갈 때마다 하나씩 증가하는 단계높이/깊이: 트리인 그래프의 최대 레벨포레스트: 트리인 그래프의 루트 노드와 가지를 제거하여 얻는 서브 트리들..
그래프의 활용최단경로 문제|E|>0인 그래프 G=(V, E)에서 꼭짓점 v₁, v₂ ∈ V 간의 가장 짧은 거리의 경로를 찾는 문제출발점(source): 경로의 시작점도착점(destination): 경로의 목적지가중치 방향 그래프가중치가 부여되지 않은 그래프: 경로의 길이(경로에 포함되는 모서리의 수)로 최단경로가중치가 부여된 경우: 가중치를 계산하여 가중치에 의해 최단거리가 결정가중치가 비용이라면 가중치의 합이 가장 작은 경로가 최단거리이고, 효과라면 가중치의 합이 큰 경로가 최단거리다익스트라 알고리즘그래프 G=(V, E)가 있을 때, V={v₁, v₂, ... , vₙ}이고 시작점이 v₁라고 가정했을 때 다익스트라 알고리즘에 사용되는 기호와 가정C[vᵢ, vⱼ]: 꼭짓점 vᵢ에서 vⱼ로 가는 가중치를..
그래프공집합이 아닌 꼭짓점(node)의 집합 V와 서로 다른 꼭짓점의 쌍(vᵢ, vⱼ)을 연결하는 모서리(edge)의 집합 E로 구성된 구조G = (V, E)V = {v₁, v₂, ... , vₙ}E = {e₁, e₂, ... , eₙ} = {(vᵢ, vⱼ), ... }G = (V, E) : 그래프 G는 꼭짓점 집합 V와 모서리 집합 E로 구성그래프 G = (V, E)에서 꼭짓점 u와 v를 연결한 모서리 e가 있을 때, 꼭짓점 u와 v는 서로 인접(adjacent)하고, 모서리 e는 꼭짓점 u와 v에 근접(incident)함루프: 인접하는 꼭짓점이 하나인 모서리 e다중 그래프: 그래프 G = (V, E)에서 두 꼭짓점 사이에 두 개 이상의 모서리가 있는 그래프방향 그래프: 화살표로 모서리를 표현해 인접하..
함수집합 A, B에 대해 집합 A에서 B로 가는 관계가 성립할 때, 집합 A의 원소 a에 대해 집합 B의 원소 b 하나가 대응되는 관계원상: 집합 B의 원소 b에 대응하는 집합 A의 원소 a상: 집합 A의 원소 a에 대해 대응되는 집합 B의 원소 b : f(a)정의역: 원상의 집합, 집합 A : dom(f)공역: 상에 대한 전체집합, 집합 B : codom(f)치역: 상의 집합, 집합 B의 부분집합 : ran(f) = {f(a) | a ∈ A}관계와 함수의 차이집합 A에서 집합 B로의관계함수집합 A(정의역)의 어떤 원소는 집합 B(공역)의 원소와 대응하지 않거나 하나 이상의 원소와 대응할 수 있음집합 A(정의역)의 모든 원소는 집합 B(공역)에서 하나의 원소와 반드시 대응해야 함단사함수Injective ..
