Difference between revisions of "Graph Theory"

Revision as of 12:21, 25 February 2026

Meme

Graph Theory

Context

Trust Graph

Taxonomy

1. By Structure:
   1. Undirected Graph: Edges have no direction; connections are bidirectional
   2. Directed Graph (Digraph): Edges have direction; connections flow one way
   3. Weighted Graph: Edges have assigned values or costs
   4. Unweighted Graph: All edges are equal; no values assigned
2. By Connectivity:
   1. Connected Graph: Path exists between every pair of vertices
   2. Disconnected Graph: Some vertices have no connecting path
   3. Complete Graph: Every vertex connects to every other vertex
   4. Tree: Connected graph with no cycles
3. By Cycles:
   1. Acyclic Graph: Contains no cycles or loops
   2. Cyclic Graph: Contains at least one cycle
   3. DAG (Directed Acyclic Graph): Directed graph with no cycles
4. By Representation:
   1. Simple Graph: No self-loops or multiple edges between vertices
   2. Multigraph: Multiple edges allowed between vertices
   3. Pseudograph: Self-loops and multiple edges allowed
5. By Application:
   1. Social Network Graph: Represents relationships between people
   2. Knowledge Graph: Represents entities and their relationships
   3. Flow Network: Models flow of resources through a network
   4. Dependency Graph: Shows dependencies between elements

References