shevlopmes's blog

By shevlopmes, history, 19 months ago, In English

Free chatGPT-4o solved the following task in less than 10 seconds:

You are given a graph, each vertex is labeled with some number $$$d_v$$$. Is it possible to orient all edges so that the out degree (number of edges oriented from a vertex) of each vertex does not exceed $$$d_v$$$?

On what topic is this task?
Ok, so what's the trick?
P.S.
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
19 months ago, hide # |
 
Vote: I like it +97 Vote: I do not like it

You are literally given a flow network. There are no limitations on the resulting graph (like connectivity), so the edges are just two vertices, of which you need to choose one, such that each vertex is chosen by no more than $$$d_v$$$ edges. This is literally a flow.

»
19 months ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

just basic flow where edge and vertex being swapped.

»
19 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Sounds more natural in terms of a matching problem, you want to match each edge with one out of 2 nodes and each node can be matched by at most $$$d_v$$$ edges.