by Albert Major

Introduction to Artificial Intelligence

Graph Theory Fundamentals

• Material corresponds to:
  • Chapter 13 in textbook 4th edition
  • Chapter 14 in textbook 3rd edition

Basic Components

• Nodes (also called vertices)
  • The points in a graph
  • Represent variables or states
  • Can hold different types of information
• Edges
  • Connections between nodes
  • Show relationships or transitions
  • Can be directed (arrows) or undirected (lines)

Graph Types

• Connected vs Disconnected
  • Connected: All nodes have some path to all other nodes
  • Disconnected: Some nodes or groups are isolated
• Directed vs Undirected
  • Directed: Edges have arrows showing direction of relationship
  • Undirected: Edges show mutual relationships
• Trees
  • Special type of graph
  • Directed, connected graph without cycles
  • Used in game trees (like tic-tac-toe states)

Graph Traversal Types

• Path
  • Can move between nodes directly or indirectly
  • Cannot visit the same node twice
  • Example: Going from node 1→2→3→4 is valid
  • Example: Going from 1→2→1→3 is invalid (revisits node 1)
• Trail
  • Can visit same nodes multiple times
  • Cannot use same edge twice
  • More flexible than a path
  • Example: Can revisit Node 1 but can't use same connection twice
• Walk
  • Most flexible traversal
  • Can use any nodes and edges
  • No restrictions on revisiting

Bayesian Networks in Detail

Definition and Properties

• Is a directed acyclic graph (DAG)
• Also known as:
  • Belief networks
  • Decision networks
  • Causal graphs