Undirected Graphs and Networks Networks and graphs

A network is a collection of objects connected to each other in some specific way. A graph is a finite set of dots called vertices (or nodes) connected by links called edges (or connections). For our purposes, a graph and a network mean the same thing. The degree (or valence) of a vertex is the number of edges attached to the vertex. A vertex of degree zero is known as an isolated vertex. The sum of the degrees of all the vertices of a graph is twice the number of edges. The number of vertices of odd degree must be even. An edge which connects a vertex to itself is called a loop and contributes two towards the degree. If two or more edges connect the same pair of vertices they are called multiple edges (or parallel edges) and all count towards the degree. More formally: a simple graph is a set of vertices V and set E of unordered pairs of distinct elements of V called edges. A network that contains multiple edges or loops is sometimes called a multigraph. A simple graph is a graph with no multiple edges or loops. The formal mathematical definition of a simple graph permits neither multiple edges or loops. A graph with one vertex and no edges is called a null graph or a trivial graph. A complete graph is a graph which has an edge joining every pair of vertices. A weighted graph is one in which each edge is assigned a non-negative number called the length or weight. In applications, this number can represent different things such as distance, cost in dollars, time taken, etc. A planar graph is a graph that can be drawn on a plane so that no edges cross