11/19/2014

Agenda

Graph

Graph Theory

Categories

Applications

Graph Properties and Measurements

References

Graph

A graph is a representation of a set of objects where some pairs of objects are connected by links.

The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.

Set of dots : Vertices(Nodes or points)

Joining lines or curves : Edges(Arcs or lines)

A graph is a set of objects called points or vertices connected by links called lines or edges

Definition: Graph

G is an ordered triple G:=(V, E, f)

V is a set of nodes, points, or vertices.

E is a set, whose elements are known as edges or lines.

f is a function

maps each element of E

to an unordered pair of vertices in V.

Definitions

Vertex

Basic Element

Drawn as a node or a dot.

Vertex set of G is usually denoted by V(G), or V

Edge

A set of two elements

Drawn as a line connecting two vertices, called end vertices, or endpoints.

The edge set of G is usually denoted by E(G), or E.

Example

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

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

Loop, Multiple edges

Loop : An edge whose endpoints are equal

Multiple edges : Edges have the same pair of endpoints

Multiple

edges

loop

7

Adjacent, neighbors

Two vertices are adjacent and are neighbors if they are the endpoints of an edge Example:

A and B are adjacent

A and D are not adjacent

8

Properties

Undirected

Simple

Graph represents a road network, the weights could represent the length of each road

Categories

Directed Graph:

The edges have a direction associated with them

Undirected Graph:

The edges have a direction associated with them

Categories

Mixed Graph:

Some edges may be directed and some may be undirected

Simple Graph:

An undirected graph without loop or multiple edges

Special Types of

Graphs

Empty Graph / Edgeless graph

No edge

Null graph

No nodes

Obviously no edge

Weighted graphs

It is a graph for which each edge has an associated weight, usually given by a weight function w: E R.

Connectivity

A graph is connected if

you can get from any node to any other by following a sequence of edges OR

any two nodes are connected by a path.

A directed graph is strongly connected if there is a directed path from any node to any other node.

Topological

Distance

A shortest path is the minimum path connecting two nodes.

The number of edges in the shortest path connecting p and q is the topological distance between these two nodes, dp,q

Graph-based

Representations

Representing a problem as a graph can provide a different point of view

Representing a problem as a graph can make a problem much simpler

More accurately, it can provide the appropriate tools for solving the problem Graph-like problems

There are two components to a graph

Nodes and edges

In graph-like problems, these components have natural correspondences to problem elements

Entities are nodes and interactions between entities are edges

Most complex systems are graph-like

Graph Theory

Study of Graphs

Concerns the relationship among lines and points

Deals with

Connection problems

Scheduling problems

Transportation problems

Network analysis

Games and Puzzles

Transportation problems

Tree and Spanning

Tree

Tree:

A