개요

그래프 이론의 시대는 잘 알려진 Königsberg Bridge 문제를 해결하기 위해 1735년 Euler와 함께 시작되었습니다. 현대 시대에 그래프 이론은 컴퓨터 과학의 필수적인 구성 요소입니다. 인공 공학, 기계 학습, 깊은 학습, 데이터 과학, 및 소셜 네트워크. 그래프 이론의 최신 응용 프로그램에서는 트래픽 네트워크, 탐색 가능한 네트워크 및 비상 대응을 위한 최적의 라우팅, 분자 역학에 대한 그래프 이론적 접근과 같은 그래프 이론의 많은 최첨단 응용 프로그램에 대해 설명합니다.

그래프 이론이란 무엇입니까? 

그래프 G(V, E)는 비선형 데이터 구조, 세트 쌍(V, E)으로 구성되며 여기서 V는 비어 있지 않은 정점(점 또는 노드) 세트입니다. E는 매핑 f가 있는 에지(선 또는 가지)의 집합입니다. 즉, 집합 E에서 V 요소의 정렬된 또는 정렬되지 않은 쌍의 집합으로의 집합입니다. 그래프의 순서라고 하는 수 간선의 수를 그래프 G(V, E)의 크기라고 합니다. 

그래프는 무방향 그래프, 방향 그래프 및 가중 그래프의 세 가지 유형이 있습니다.

• 무방향 그래프: 무방향 그래프에서 가장자리는 정렬되지 않은 정점 쌍과 연결됩니다. 루프와 평행 모서리가 없는 그래프 G(V, E)를 단순 그래프라고 합니다. 정점 쌍 사이에 둘 이상의 간선이 있는 그래프를 다중 그래프라고 합니다. 다시 말하지만 다중 그래프에 루프가 포함되어 있으면 그래프는 의사 그래프입니다. 무방향 그래프는 구조에 따라 Null 그래프, 완전 그래프, 정규 그래프, 이분 그래프, 사이클, 휠, 오일러 그래프, 해밀턴 그래프 등 다양한 유형이 있습니다.
• 유향 그래프: 유향 또는 이중 그래프 G는 eϵE가 정점의 정렬된 쌍과 연결되도록 정점 집합 V와 가장자리 집합 E로 구성됩니다. 즉, 각 가장자리에는 방향이 있습니다. 다양한 유형의 유향 그래프가 있습니다. 대칭 유향 그래프, 단순 유향 그래프, 완전한 유향 그래프, 준이행 이중 그래프 및 방향 그래프.
• 가중 그래프: 많은 그래프에는 비용, 거리 및 수량과 같은 실제 영향을 나타내는 관련 가중치가 포함된 에지가 있을 수 있습니다. 가중 그래프는 유향 또는 무향 그래프일 수 있습니다.
• 트리는 가장 일반적으로 사용되는 그래프의 하위 범주 중 하나입니다. 컴퓨팅에서 트리는 데이터베이스에서 데이터를 구성하고 저장하는 데 유용합니다. 트리는 순환이 없는 연결된 비순환 그래픽입니다. n개의 정점을 가진 트리 T는 n-1개의 가장자리를 가집니다. 하위 그래프 T 연결된 그래프 G(V, E)는 T가 트리이고 G의 모든 정점을 포함하는 경우 스패닝 트리라고 합니다. 두 가지 알고리즘이 있습니다. a) BFS(Breadth-first search) 및 b) DFS(Depth-first search) 첫 번째 검색) 주어진 무향 그래프 G의 스패닝 트리를 구성하기 위한 것입니다. 가중 그래프의 경우 Prim과 Kruskal의 알고리즘을 사용하여 최소 스패닝 트리를 구성할 수 있습니다. 하나의 정점이 XNUMX차이고 다른 정점이 XNUMX차 또는 XNUMX차인 이진 트리는 대수식 및 저장 표현을 나타내는 데 사용됩니다. 이진 트리의 저장 표현에는 a) 순차 표현과 b) 링크 표현의 두 가지 방법이 있습니다.

전. 이진 트리를 사용하여 식 ((a + b)* c) + (d/e)를 나타냅니다.

그래프 이론은 어떻게 작동합니까?

그래프 이론은 궁극적으로 서로 다른 노드(정점)와 연결(에지) 사이의 관계를 연구하는 것입니다. 구조 전반에 걸친 그래프 연구는 레이아웃, 네트워킹, 최적화, 매칭 및 운영의 수많은 문제에 대한 답을 제공합니다.

그래프 색칠 문제 

그래프 채색은 인접한 정점이 다른 색상을 얻는 가장 유용한 기술 중 하나입니다. 그래프의 올바른 색상 지정에 사용되는 최소 색상 수는 최적화 문제인 우리의 목표입니다.

그래프 채색 문제는 일정 또는 시간표 만들기, 모바일 무선 주파수 할당, 스도쿠, 레지스터 할당 및 지도 채색과 같은 많은 응용 프로그램이 있습니다.

시간 예약 문제 

특정 학기에 대해 생각해 보십시오. 다음과 같은 각 주제 조합을 수강하는 학생들이 있습니다. 이 문제에서 우리의 목표는 8개 과목에서 시험 일정을 잡기 위한 최소 시험 일수를 찾아 주어진 과목 조합 중 하나를 선택하는 학생들이 충돌하지 않도록 하는 것입니다.

또한 최소 일수를 사용하여 가능한 일정을 찾으십시오.

표: 주제 조합

문제의 결과

그래프 이론의 고전적 문제

• 오래된 문제는 1개의 주택 H2, H3, H4, HXNUMX를 수도(W), 가스(G), 전기(E), TV 케이블 라인(C) 등 각각 XNUMX개의 유틸리티에 연결하는 것입니다. 각 서비스가 두 집 사이에 두 개의 교차 연결 없이 네 집 각각에 연결될 수 있습니까?

• 여행하는 세일즈맨 문제:

판매자의 영역에 이들 도시의 일부 쌍을 연결하는 고속도로가 있는 여러 도시가 포함되어 있다고 가정합니다. 그는 모든 도시를 한 번씩 방문해야 합니다. 그래프 이론은 이 운송 시스템을 해결하는 데 유용할 수 있습니다. 문제는 정점이 도시에 해당하는 그래프 G로 그래픽으로 나타낼 수 있습니다. 두 정점은 고속도로가 해당 도시를 연결하는 경우에만 가장자리로 연결됩니다. 정점 a에서 시작하여 세일즈맨은 가장자리 e1,e2, e3, e4, e5 및 e6을 취하여 다시 정점 a로 돌아갈 수 있습니다.

현대 실생활 응용을 위한 알고리즘 

Google지도

Google 지도는 건설 및 운송 시스템에 그래프를 사용합니다. 두 개(또는 그 이상) 도로의 교차점은 정점으로 간주되고 두 정점을 연결하는 도로는 가장자리로 간주됩니다. 그런 다음 내비게이션 시스템은 알고리즘을 사용하여 두 정점 사이의 최단 경로를 계산합니다. GPS에서는 DFS(깊이 우선 검색) 및 BFS(호흡 우선 검색) 알고리즘과 같은 다른 최단 경로 알고리즘도 사용합니다. 의해 Dijkstra 알고리즘, 그래프에서 주어진 노드(소스 노드)와 다른 모든 노드(목적지 노드) 사이의 최단 경로를 찾을 수 있습니다. 이 알고리즘은 에지 가중치를 사용하여 소스 노드와 다른 모든 노드 간의 총 거리(가중치)를 줄이는 방법을 찾습니다.

페이스북과 링크드인

Facebook이 어떤 사람이 당신의 공통 친구인지 어떻게 아는지 또는 LinkedIn이 연결이 두 번째인지 세 번째인지 어떻게 아는지 궁금한 적이 있습니까? Facebook과 LinkedIn은 각 정점이 사용자 프로필인 그래프로 사용자를 모델링합니다. 두 사람 사이의 가장자리는 그들이 서로 친구이거나 서로를 따른다는 사실입니다. Facebook 및 LinkedIn 친구 제안 알고리즘은 그래프 이론을 사용합니다. 페이스북은 무방향 그래프의 한 예입니다. 

월드 와이드 웹

World Wide Web에서 웹 페이지는 정점으로 간주됩니다. 페이지 'v'에서 페이지 'u'로의 링크가 있는 경우 페이지 'u'와 다른 페이지 'v' 사이에 가장자리가 있습니다. 방향 그래프의 예입니다. 이것이 Google Page Rank 알고리즘의 기본 개념입니다.

Social Network

소셜 네트워킹 사이트에서는 그래프를 사용하여 사용자 정보를 추적합니다. 선호하는 게시물 제안, 추천 등을 보여주는 좋아요. 따라서 그래프를 관리하는 알고리즘의 개발은 정보 기술 분야에서 큰 관심을 끌고 있습니다.

결론

건강 과학, 사회 과학, 제조 산업, 국방 서비스 및 다양한 정부 활동과 같은 다양한 분야에서 인공 지능, 기계 학습, 딥 러닝, 데이터 과학 및 암호화의 적용이 증가함에 따라 그래프 이론적 접근 방식과 그 적용은 연구원에게 매우 까다로운 주제입니다. 그래프 이론 학습을 마친 학생들은 그래프 이론 지식을 현대 과학의 다양한 분야에 적용할 수 있습니다.

• SEO 기반 콘텐츠 및 PR 배포. 오늘 증폭하십시오.
• 플라토 블록체인. Web3 메타버스 인텔리전스. 지식 증폭. 여기에서 액세스하십시오.
• 출처: https://www.mygreatlearning.com/blog/application-of-graph-theory/