A Tour Through Graph Theory

From KirkWiKi
Jump to navigation Jump to search

A graph G consists of two sets:

  • V(G), called the vertex set
  • E(G), called the edge set.

An edge, denoted xy, is an unordered pair of vertices. We will often use G or G = (V;E) as short-hand.

  • If xy is an edge, then x and y are endpoints for that edge. x is incident to edge e if x is an endpoint of e.
  • Adjacent edges: share the same endpoint
  • Adjacent vertices: share the same edge
  • If two vertices are adjacent, they are called neighbors, N(x)
  • Isolated vertex: not incident to any edge
  • Loop: both endpoints of an edge are the same vertex
  • Multi-edge: more than one edge with the same endpoints
  • Simple graph: no multi-edges or loops
  • Degree of a vertex: number of edges incident to vertex, deg(v)
    • Loop adds 2 to degree

Bipartite graph: interactions between two distinct types of groups