Graphs and Networks: Paths, Circuits, Weighted Graphs and Coloring
Graphs represent objects as vertices and connections as edges. In an undirected graph, edges have no direction.
Summary
Graphs represent objects as vertices and connections as edges. In an undirected graph, edges have no direction. Edge weights can represent distance, cost, or travel time.
A path is a sequence of adjacent vertices without repeated vertices. A circuit is a closed trail with no repeated edges. A cycle returns to its starting vertex without repeating any other vertex.
| Network problem | Required coverage | Endpoint condition |
|---|---|---|
| Euler circuit | Every edge exactly once | Same starting and ending vertex |
| Open Euler trail | Every edge exactly once | Different endpoints |
| Hamilton cycle | Every vertex exactly once before returning | Same starting and ending vertex |
For a connected undirected graph, an Euler circuit exists exactly when every vertex has even degree. An open Euler trail exists exactly when two vertices have odd degree.
The total weight of a path is . A shortest weighted path minimizes this total, which need not mean using the fewest edges.
🧠 Key Concepts
- Paths
- Circuits
- Cycles
- Euler Circuits
- Open Euler Trails
- Hamilton Cycles
- Weighted Paths
- Chromatic Number
🧠 Quick Check
See what you remember from the summary.
Which best describes the difference between an Euler circuit and a Hamilton cycle?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Graphs and Networks: Paths, Circuits, Weighted Graphs and Coloring
📘 Overview A graph represents a network using vertices for objects and edges for connections. In an undirected graph, edges have no direction; edge weights can represent distance, cost, or travel time. Paths, circuits, and coloring describe different constraints on movement and relationships within a network.
🧠 Key Idea Euler problems require visiting every edge, while Hamilton problems require visiting every vertex. Weighted problems optimize total cost, whereas coloring problems assign different labels to adjacent vertices.
⚔️ Core Details: - A path is a sequence of adjacent vertices with no repeated vertices. - A circuit is a closed trail: it starts and ends at the same vertex without repeating an edge. - A connected undirected graph has an Euler circuit exactly when every vertex has even degree. - A Hamilton cycle visits every vertex exactly once before returning to its starting vertex. - The total weight of a path is
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🗄️ BS Information Systems — 1st Year
Browse this Review Set →More Computer Engineering notes
See all →More in Mathematics
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.