(→Graphs) |
|||
| Line 25: | Line 25: | ||
'''Special Types of Graphs:''' | '''Special Types of Graphs:''' | ||
| + | |||
k-regular graphs (every vertex has degree k) | k-regular graphs (every vertex has degree k) | ||
| + | |||
Complete graphs (K_n) | Complete graphs (K_n) | ||
| + | |||
Cycles (C_n - polygon with n edges/vertices) | Cycles (C_n - polygon with n edges/vertices) | ||
| + | |||
Wheels (W_n - C_n plus a new vertex linked to all vertices of C_n) | Wheels (W_n - C_n plus a new vertex linked to all vertices of C_n) | ||
| + | |||
Bipartite Graphs (G is bipartite if the vertex set can be split into V_1 and V_2 such that all edges of G to from V_1 to V_2) | Bipartite Graphs (G is bipartite if the vertex set can be split into V_1 and V_2 such that all edges of G to from V_1 to V_2) | ||
| + | |||
Complete Bipartite Graphs (A bipartite graph where every vertex in V_1 is connected to every vertex in V_2 without loops nor multiple edges) | Complete Bipartite Graphs (A bipartite graph where every vertex in V_1 is connected to every vertex in V_2 without loops nor multiple edges) | ||
Revision as of 16:34, 16 November 2008
Graphs
Definition: A graph is a collection of things (usually called vertices) together with a collection of pairs of vertices (called edges)
Note: Edges are NOT geometric => no specific shape, form length
Graphs can/do have many different visualization
A simple graph is the one without loops, without multiple edges.
The degree of a vertex, deg(v) = 2 x # of loops based at v + 1 x # of nonloop edges involving v
For an undirected graph, G, with n vertices, $ \sum_{i=0}^ndeg(v_i)=2E $
--Jniederh 00:08, 3 November 2008 (UTC)
Def: Given G with vertices v_1,...., v_k edges {e_ij)an edge between v_i and v_j, then the adjency matrix A is the square k X k matrix whose i-j-entry is # of edges from v_i to v_j
Special Types of Graphs:
k-regular graphs (every vertex has degree k)
Complete graphs (K_n)
Cycles (C_n - polygon with n edges/vertices)
Wheels (W_n - C_n plus a new vertex linked to all vertices of C_n)
Bipartite Graphs (G is bipartite if the vertex set can be split into V_1 and V_2 such that all edges of G to from V_1 to V_2)
Complete Bipartite Graphs (A bipartite graph where every vertex in V_1 is connected to every vertex in V_2 without loops nor multiple edges)
