Graph Theory

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
   5. Trust Graph: Allows evaluation or attestation of Entities (Nodes)

Node (Vertex): A fundamental point or entity in a graph that represents an object or data point

Edge (Link/Arc): A connection between two vertices that represents a relationship or path

Degree: The number of edges connected to a vertex

In-degree: Number of incoming edges (directed graphs)

• Out-degree: Number of outgoing edges (directed graphs)
• Weight: A numerical value assigned to an edge representing cost, distance, or strength

Path: A sequence of vertices connected by edges

Tree: A connected, acyclic graph where any two vertices are connected by exactly one path

Cycle: A path that starts and ends at the same vertex

Loop (Self-loop): An edge that connects a vertex to itself

Adjacent Vertices: Two vertices connected by an edge

Neighbor: A vertex directly connected to another vertex

Subgraph: A graph formed from a subset of vertices and edges from a larger graph

Connected Component: A maximal set of vertices where each pair has a connecting path

Root: The top vertex in a tree structure

Leaf: A vertex with degree 1 in a tree (no children)