Flashcards on Operations Research: Theory and Applications
Operations Research: Theory and Applications for Students
Tap to flip · Swipe to navigate
Graph Theory
31 cards
Card 1
Question: What does it mean when total supply equals total demand in a network model and what do you do if not?
Answer: Total supply equals total demand; if not, add a dummy source or destination.
Card 2
Question: What is the key idea of the Chinese Postman problem for converting a non-Eulerian graph to Eulerian?
Answer: Find odd-degree vertices, pair them with shortest paths of minimum total weight, duplicate those paths so all vertex degrees become even.
Card 3
Question: What is an odd-degree vertex?
Answer: A vertex connected to an odd number of edges.
Card 4
Question: Define an Eulerian circuit.
Answer: A closed route that starts and ends at the same vertex and uses every edge exactly once.
Card 5
Question: What is the difference between a path and a cycle? Give examples.
Answer: A path has no repeated vertices (e.g. A-B-C). A cycle starts and ends at the same vertex (e.g. A-B-C-A).
Card 6
Question: In which models are paths and cycles typically used?
Answer: Paths are used in shortest path and routing; cycles are used in Chinese postman, tours, and circuit problems.
Card 7
Question: Define a complete graph.
Answer: A graph where every pair of distinct vertices is connected by an edge.
Card 8
Question: What is the chromatic number of a complete graph Kn?
Answer: n
Card 9
Question: What is a weighted graph?
Answer: A graph where edges or vertices have numerical values such as cost, time, distance, or capacity.
Card 10
Question: What are different interpretations of weights on a graph?
Answer: Weights can mean distance (routing), time (scheduling), cost (transportation), or capacity (flow networks).