Mixed Chinese Postman Problem¶
Find a least-cost closed walk covering every link of a weighted graph with undirected edges and directed arcs.
Core Idea¶
The mixed Chinese postman problem asks for the least-cost closed walk covering every edge and arc of a weighted mixed graph at least once. Undirected edges may be traversed either way, while directed arcs must be followed in their assigned direction. Links can be repeated, with those repetitions included in total cost. The reusable identity is the graph input, all-link coverage, legal closed walk and minimization objective—not a particular route or algorithm.
Scope of Application¶
The problem models services that must cover network segments, such as a route through modeled one-way and two-way streets. Its mathematical instances need no physical street map. Purely directed and purely undirected networks are simpler special cases of a mixed-graph formulation; truly mixed cases combine both link types and their orientation constraints.
Clarity¶
Visiting every intersection does not satisfy the requirement to traverse every required link. A feasible tour is not necessarily a minimum-cost tour. The standard formulation assumes a strongly connected mixed graph so a direction-respecting closed coverage walk exists. Its common NP-complete claim concerns the decision version; the optimization problem is NP-hard.
Manages Complexity¶
The graph abstraction reduces many route choices to declared link directions, costs, coverage duties and closed-walk feasibility. This makes solutions comparable while exposing modeling errors: a misclassified one-way road or omitted service segment can make a mathematically optimal answer operationally wrong.
Abstract Reasoning¶
Check link coverage and legal direction before comparing costs. In a three-vertex cycle with arc A→B and undirected edges B—C and C—A, each of unit weight, the walk A→B→C→A covers everything once at cost three. Because every required link already contributes one unit, this walk meets the lower bound and is optimal for that small instance.
Knowledge Transfer¶
Different arc-service settings reuse the problem when their links, direction rules and service obligations can be mapped faithfully to a mixed graph. The wider feasible-set-plus-objective relation belongs to Optimization Problem; the mixed graph and all-link closed tour remain specific to this routing family.
Relationships to Other Abstractions¶
Current abstraction Mixed Chinese Postman Problem Domain-specific
Parents (1) — more general patterns this builds on
-
Mixed Chinese Postman Problem is a kind of Optimization Problem Domain-specific
The mixed Chinese postman problem has a feasible set of closed coverage walks and a minimum traversal-cost objective.
Hierarchy path (1) — routes to 1 parentless root
- Mixed Chinese Postman Problem → Optimization Problem → Optimization
Neighborhood in Abstraction Space¶
Mixed Chinese Postman Problem sits in a sparse region of the domain-specific corpus (76th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Edge Covering Number — 0.85
- Comparability Graph — 0.83
- A-star algorithm — 0.83
- Geodetic Graph — 0.83
- Graph Embedding — 0.83
Computed from structural-signature embeddings · 2026-10-08