Graph theory fundamentals lay the groundwork for understanding complex networks. We'll dive into the basic building blocks: vertices and edges. These elements combine to form various graph types, each with unique properties and applications.

We'll explore directed and undirected graphs, vertex characteristics, and connectivity concepts. These ideas are crucial for modeling real-world systems, from social networks to transportation routes. Get ready to uncover the power of graphs in solving everyday problems!

Graph Components

Fundamental Elements of Graphs

• Vertex represents a point or node in a graph structure
  • Forms the basic unit of a graph
  • Can represent entities (cities, people, data points)
• Edge connects two vertices in a graph
  • Represented as a line or arc between vertices
  • Models relationships or connections between entities
• Graph consists of a set of vertices and edges
  • Represented as G = (V, E) where V is vertex set and E is edge set
  • Visualized as diagrams with points and lines

Graph Characteristics and Classifications

• Order of a graph denotes the number of vertices
• Size of a graph indicates the number of edges
• Edge types include loops (self-connections) and multiple edges (parallel connections)
• Simple graph contains no loops or multiple edges
• Multigraph allows loops and multiple edges
• Representation methods include adjacency matrices and adjacency lists

Directed vs Undirected Graphs

Undirected Graphs

• Edges have no orientation in undirected graphs
• Connections between vertices are bidirectional
• Represented by lines without arrows
• Model symmetric relationships (friendship networks, road connections)

Directed Graphs

• Edges have specific direction in directed graphs (digraphs)
• Represented by arrows pointing from one vertex to another
• Edges called arcs or directed edges to emphasize orientation
• In-degree counts edges pointing towards a vertex
• Out-degree counts edges pointing away from a vertex
• Model one-way relationships (social media follows, network traffic flow)

Mixed Graphs

• Contain both directed and undirected edges
• Model complex real-world scenarios (transportation networks with one-way and two-way streets)
• Flexibility in representing various types of relationships within a single graph structure

Vertex Properties

Adjacency and Incidence

• Adjacent vertices directly connected by an edge
• Incident edge connects a given vertex to another vertex
• Adjacency matrix represents vertex connections in a square matrix
• Incidence matrix shows relationships between vertices and edges

Vertex Degree

• Degree of a vertex counts incident edges
• Undirected graphs degree equals number of incident edges
• Directed graphs total degree sums in-degree and out-degree
• Handshaking lemma states sum of all vertex degrees equals twice the number of edges
• Isolated vertex has degree zero (no connections)
• Leaf or pendant vertex has degree one (single connection)

Paths, Cycles, and Connectivity

Paths and Cycles

• Path sequence of connected vertices without repetition
• Path length determined by number of edges
• Cycle starts and ends at same vertex
• Simple path or cycle avoids vertex repetition (except start/end for cycles)
• Eulerian path traverses every edge exactly once
• Hamiltonian path visits every vertex exactly once

Graph Connectivity

• Connectivity existence of paths between vertices
• Connected graph has path between every vertex pair
• Component maximal connected subgraph
• Bridge edge whose removal disconnects the graph
• Articulation point vertex whose removal increases number of components
• Strong connectivity in directed graphs requires paths in both directions between all vertex pairs