Prab: CSV import

2024-04-15T20:04:13Z

CSV import

New page

[[File:6n-graf.svg|thumb|6n-graf]] [[File:Undirected.svg|left|thumb|Undirected]] [[File:Directed.svg|thumb|Directed]] [[File:Wikipedia_multilingual_network_graph_July_2013.svg|thumb|Wikipedia multilingual network graph July 2013]] [[File:Moreno_Sociogram_2nd_Grade.png|thumb|Moreno Sociogram 2nd Grade]] '''Graph theory''' is a fundamental area of [[mathematics]] and [[computer science]] that involves the study of [[graphs]], which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '''vertices''' (also called nodes or points) which are connected by '''edges''' (also called links or lines). Graph theory has applications in various fields, including [[biology]], [[computer network]]s, [[social sciences]], and [[linguistics]], to name a few.

==Definition==
A '''graph''' \(G\) is an ordered pair \(G = (V, E)\) comprising a set \(V\) of vertices or nodes together with a set \(E\) of edges or arcs, which are 2-element subsets of \(V\) (i.e., an edge is associated with two vertices, and the order of the vertices does not matter). If the order of the vertices matters, the graph is called a '''directed graph''' or '''digraph''', and the edges are called directed edges or arcs.

==Types of Graphs==
Graphs can be classified in many ways. Some of the most common classifications include:

* '''Simple Graphs''' - A graph in which each edge connects two distinct vertices and where no two edges connect the same pair of vertices.
* '''Multigraphs''' - Graphs that may have multiple edges connecting the same vertices.
* '''Weighted Graphs''' - Graphs where each edge is assigned a weight or cost.
* '''Directed Graphs''' (Digraphs) - Graphs where the edges have a direction, from one vertex to another.
* '''Complete Graphs''' - A simple graph in which every pair of distinct vertices is connected by a unique edge.

==Basic Concepts==
Some basic concepts in graph theory include:

* '''Adjacency''': Two vertices are adjacent if they are connected by an edge.
* '''Path''': A sequence of edges which connects a sequence of vertices.
* '''Cycle''': A path that starts and ends at the same vertex, with all edges and vertices being distinct.
* '''Connected Graph''': A graph is connected if there is a path between every pair of vertices.
* '''Graph Isomorphism''': Two graphs are isomorphic if there is a bijection between the vertex sets of the two graphs that preserves adjacency.

==Applications==
Graph theory is used in many areas, including:

* '''Computer Networks''': To model and analyze the structure of the internet and other communication networks.
* '''Social Networks''': To analyze the relationships between individuals or organizations.
* '''Biology''': To model the structures of molecules, the spread of diseases, and ecological networks.
* '''Transportation and Logistics''': To find the most efficient routes and schedules.
* '''Algorithms''': Many algorithms in computer science are based on graph theoretical concepts, such as searching and sorting.

==History==
Graph theory originated in the 18th century with the work of [[Leonhard Euler]] on the [[Königsberg bridge problem]], which led to the concept of the Eulerian path. The field has since grown and diversified, touching many disciplines and contributing to the development of many areas of mathematics and science.

==See Also==
* [[Network theory]]
* [[Topology]]
* [[Combinatorics]]
* [[Algorithm]]

[[Category:Graph Theory]]
[[Category:Mathematics]]
[[Category:Computer Science]]

{{math-stub}}

Graph theory - Revision history

Prab: CSV import