Graph theory

6n-graf

Undirected

Directed

Wikipedia multilingual network graph July 2013

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 networks, 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