Graphs at University Of Edinburgh | Flashcards & Summaries

Select your language

Suggested languages for you:
Log In Start studying!

Lernmaterialien für Graphs an der University of Edinburgh

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

TESTE DEIN WISSEN

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

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

What is a sink in a directed graph?


Lösung anzeigen
TESTE DEIN WISSEN

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

Lösung ausblenden
TESTE DEIN WISSEN

What is a name for a directed edge sometimes used?


Lösung anzeigen
TESTE DEIN WISSEN

An arc.

Lösung ausblenden
TESTE DEIN WISSEN

What is a plainer embedding and a plainer graph?


Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

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


Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

How can you create 2d arrays in python?

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

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


Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

What is Krakowski’s criterion for planer graphs?


Lösung anzeigen
TESTE DEIN WISSEN

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

Lösung ausblenden
TESTE DEIN WISSEN

What is a connected component of a graph G?

Lösung anzeigen
TESTE DEIN WISSEN
That is a connected subset of the graph which we can't add any more vertices to without making it unconnected. 
Lösung ausblenden
TESTE DEIN WISSEN

What is a graph?

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

What is a connected graph?

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

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

Lösung anzeigen
TESTE DEIN WISSEN

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

Lösung ausblenden
  • 5951 Karteikarten
  • 322 Studierende
  • 15 Lernmaterialien

Beispielhafte Karteikarten für deinen Graphs Kurs an der University of Edinburgh - von Kommilitonen auf StudySmarter erstellt!

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.

Mehr Karteikarten anzeigen
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.

Graphs

Erstelle und finde Lernmaterialien auf StudySmarter.

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

Jetzt loslegen

Das sind die beliebtesten Graphs Kurse im gesamten StudySmarter Universum

Study Designs & Graphs

University of South Australia

Zum Kurs
Gram +

Aristotle University of Thessaloniki

Zum Kurs
Graphics

Mansoura University

Zum Kurs
Gram -

Pontificia Universidad Catolica de Chile

Zum Kurs
Gram (-)

Universidad de La Frontera

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Graphs
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Graphs