Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Graphs Kurs an der University of Edinburgh zu.

- 5951 Karteikarten
- 322 Studierende
- 15 Lernmaterialien

Q:

What is an example of a task that is solved by a topological order of a graph?

A:

A topological sort can solve a program of taksing requiring other tasks to be done first. If we draw a directed graph where a prerequesite task points to tasks it is required for we can find the set of possible tolpilogical orders to be all the orders that solve this problem.

Q:

What is a sink in a directed graph?

A:

A sink node is a node with only arcs going in.

Q:

What is a name for a directed edge sometimes used?

A:

An arc.

Q:

What is a plainer embedding and a plainer graph?

A:

A plainer graph is a graph that can be laid out on a plain without any crossing edges. A non-plainer graph does have crossing edges.

Q:

What are some examples of graph structures in the real world?

A:

For example road networks with roads being networks and nodes being intersections, computer networks where the connections between computers are the edges and computers are the nodes and the world wide web with hyperlinks being edges and webpages being the edges.

Q:

How can you create 2d arrays in python?

A:

You could create a 1d array and map it to a 2d array that is (i, j) = j * n + i. Or you could import NumPy and use that.

Q:

What do we mean when we say in(v) and out(v)?

A:

In(v) is the number of edges going into some vertex v. Then out(v) is the number of edges going out of some vertex v.

Q:

What is Krakowski’s criterion for planer graphs?

A:

It says that |E| <= 3|V| - 6

Q:

What is a connected component of a graph G?

A:

That is a connected subset of the graph which we can't add any more vertices to without making it unconnected.

Q:

What is a graph?

A:

A graph is a mathematical structure consisting of a set of vertices and a set edges. So G = (V, E) where V is a set and E (< V x V.

Q:

What is a connected graph?

A:

A graph is connected when for any nodes A and B in the graph there is a path made out of edges between them. In the case of a directed graph these edges must be traversed in order for all possible pairs. That is from any node you can reach any other.

Q:

How do we find the connected components of an undirected graph?

A:

We can apply either DFS or BFS so simple find the all the elements than are connected to some vertex in some way.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen