7 Graph

Nodes (vertices) and Edges are the basic items inside a graph. Node represents the endpoint inside the graph. Edge is using to make a connection between two nodes. For any node, it can be connected by any numbers of edges.

Node properties

Node properties
 Neighbors Neighbors of a node are the nodes directly connect to that node by an edge. Degree Degree of a node is the number of edges connected to the node. Or how many neighbors that node has. Eccentricity Eccentricity of a node x is the biggest shortest distance between v and any other node.
Graph properties
 Path A sequence of edges which can form a connection between two nodes. Distance Distance between two nodes. Minimum number of edges can be used to form a path between two nodes. Cycle A path which start node and end node are same. Eulerian path A path which pass though every edge on the graph once Eulerian cycle A cycle which pass though every edge on the graph once Hamiltonian path A path which visit every vertices on the graph once Hamiltonian cycle A cycle which pass though every vertices on the graph once Radius minimum eccentricity of all nodes in the graph.
Type of graphs
 Simple graph There are at most one edge between a pair of nodes. Multi graph There are more than one edge between a pair of nodes. Contain self-loop, which means the two heads of an edge may connecting to same node. Connected Graph For each pair of nodes, a path exists between them. Directed Graph The connection between two nodes is only one-way relationship. Strong Connected Graph In a directed graph. For any pairs of nodes A and B. There are paths from A to B and fromB to A. Tree A graph is connected and doesn’t contain any cycle. Weight Graph Every edges in the graph have been assigned a number, which are the weight of that edges. Planar Graph A graph that can be embebbed on the plane with no edges cross each other Bipartite Graph A graph that nodes can be divided into two disjoint sets such that no edge connects the nodes in the same set.

Problems

 1. Traversal Algorithms for travelling nodes in a graph 2. Cycle Find the graph contain cycle or not / Find the graph is tree or not 3. Topological Ordering For a directed acyclic graph, find the order of all nodes. For every edge form x to y, x is before y in the order 4. Strong Connected Component 5. Shortest Path 6. Minimum Spanning Tree 7. Matching
 © The University of Hong Kong Algorithms Library - hkual@cs.hku.hk