Graphs are made up of vertices and edges, representing entities and their connections. Understanding these components is crucial for analyzing network structures in various fields, from social networks to transportation systems.
Vertex properties, like degree, provide insights into a graph's structure. Degree measures a vertex's connectivity, while concepts like indegree and outdegree in directed graphs reveal the flow of information or resources within a network.
Graph Components and Vertex Properties
Vertices and edges
- Vertices (nodes) form fundamental elements representing entities or points depicted as dots or circles (cities in a transportation network)
- Edges connect vertices representing relationships or links typically shown as lines or arrows (roads connecting cities)
- Graph notation expressed as $G = (V, E)$ where $V$ represents set of vertices and $E$ represents set of edges
- Types of graphs based on edge properties include undirected graphs with no directional edges and directed graphs (digraphs) with specific directional edges (social network connections vs one-way streets)
Degree of a vertex
- Degree defines number of edges incident to a vertex denoted as $deg(v)$ for a vertex $v$
- Degree properties range from minimum degree 0 for isolated vertices to maximum degree $|V| - 1$ for vertices connected to all others
- Handshaking lemma states sum of degrees of all vertices equals twice the number of edges: $\sum_{v \in V} deg(v) = 2|E|$
- Degree sequence lists vertex degrees in non-increasing order
- Regular graphs feature all vertices with same degree (cube graph)
Calculating vertex degrees
- Simple graph examples:
- Path graph end vertices have degree 1 others have degree 2
- Cycle graph all vertices have degree 2
- Complete graph $K_n$ all vertices have degree $n-1$
- Special graph structures:
- Star graph central vertex has degree $n-1$ others have degree 1
- Wheel graph central vertex has degree $n-1$ others have degree 3
- Bipartite graphs may have different degrees for vertices in each partition
- Multigraphs count multiple edges between same pair of vertices
- Loops contribute 2 to degree of vertex
Indegree vs outdegree
- Indegree counts number of edges pointing towards a vertex denoted as $deg^-(v)$ (incoming emails)
- Outdegree counts number of edges pointing away from a vertex denoted as $deg^+(v)$ (outgoing emails)
- Total degree in directed graphs sums indegree and outdegree: $deg(v) = deg^-(v) + deg^+(v)$
- Balanced vertices have equal indegree and outdegree
- Source vertices have indegree 0 while sink vertices have outdegree 0 (starting and ending points in a flow network)
- Directed graph properties: sum of all indegrees equals sum of all outdegrees both equaling total number of edges in graph