Untitled Document

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

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