FACTOID # 11: Oklahoma has the highest rate of women in State or Federal correctional facilities.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Vertex (graph theory)
This article just presents the basic definitions. For a broader view see graph theory.
For another mathematical use of "graph", see graph of a function.
A graph with 6 vertices and 7 edges.
A graph with 6 vertices and 7 edges.

In mathematics and computer science a graph is the basic object of study in graph theory. Informally, a graph is a set of objects called vertices connected by links called edges. Typically, a graph is depicted as a set of dots (the vertices) connected by lines (the edges). Depending on the application some edges can directed.

Contents

Definitions

Definitions in graph theory vary in the literature. Here are the conventions used in this encyclopedia.


Undirected graph

An undirected graph or graph G is an ordered pair G:=(V, E) with

  • V a set of vertices or nodes,
  • E a set of unordered pairs of distinct vertices, called edges or lines.

Directed graph

A directed graph, digraph or quiver G is an ordered pair G:=(V,A) with

  • V a set of vertices or nodes,
  • A a set of ordered pairs of vertices called directed edges, arcs or arrows.

Note that a directed graph is allowed to have loops, that is, edges where the start and end vertices are the same.


Mixed graph

A mixed graph G is a 3-tuple G:=(V,E,A) with V, E and A defined as above.


Variations in the definitions

As defined above, edges of undirected graphs have distinct ends, and E and A are sets (with distinct elements as sets always do). Many applications require more general possibilities, but terminology varies. A loop is an edge (directed or undirected) with both ends the same; these may be permitted or not permitted according to the application. Sometimes E or A are allowed to be multisets, so that there can be more than one edge between the same two vertices. The unqualified word "graph" might allow or disallow multiple edges in the literature, according to the preferences of the author. If it is intended to exclude multiple edges (and, in the undirected case, to exclude loops), the graph can be called simple. On the other hand, if it is intended to allow multiple edges, the graph can be called a multigraph. Sometimes the word pseudograph is used to indicate that both multiple edges and loops are allowed.


Further definitions

For more definitions see Glossary of graph theory.

Two edges of a graph are called adjacent (sometimes coincident) if they have a common vertex. Similarly, two vertices are called adjacent if they are the ends of the same edge. An edge and a vertex on that edge are called incident.


The graph with only one vertex and no edges is the trivial graph. A graph with only vertices and no edges is known as an empty graph; the graph with no vertices and no edges is the null graph, but not all mathematicians allow this concept.


In a weighted graph or digraph, each edge is associated with some value, variously called its cost, weight, length or other term depending on the application; such graphs arise in many contexts, for example in optimal route problems such as the traveling salesman problem.


Normally, the vertices of a graph by their nature are undistinguishable. (Of course, they may be distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges). Some branches of graph theory require to uniquely identify vertices. If each vertex is given a label, then the graph is said to be a vertex-labeled graph, whereas graphs which have labeled edges are called edge-labeled graphs. Graphs with labels attached to edges or vertices are more generally designated as labeled. Consequently, graphs without labels are called unlabelled.


Examples

Image:6n-graf.png
The picture is a graphic representation of the following graph

  • V:={1,2,3,4,5,6}
  • E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,5}}

Important graphs

Generalizations

In a hypergraph, an edge can connect more than two vertices.


An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.


Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs.


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.


  Results from FactBites:
 
Degree (graph theory) - Wikipedia, the free encyclopedia (212 words)
In the mathematical field of graph theory the degree or valency of a vertex v is the number of edges incident to v (with loops being counted twice).
In a directed graph the indegree of a vertex v is the number of edges terminating at v and the outdegree is the number of edges originating at v.
If each vertex of the graph has the same degree k the graph is called a k-regular graph and the graph itself is said to have degree k.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m