Graph Basics
More Graph Basics
Moving on a graph
Ms Shaw's Favourites
Networks
100

What is a simple graph? Draw an example

Simple graphs do not have any loops. There are no duplicate or multiple edges either.


100
List one variation of Euler's Formula. What is it used for?

v+f=e+2

f=e-v+2

v=e-f+2

e=v+f-2

Used to check if a graph is in Planar form

100

What is the definition of a trail?

  • No edges repeated
  • Vertices may be repeated
100

What is odontophobia the fear of?

Dentistry 

100

How many edges does a minimum spanning tree have?

One less than the number of vertices

200

What is a degenerated graph? Draw an example

Degenerate graphs have all vertices isolated. This means that there are no edges in the graph at all.

200

Look at the graph. What is the degree of Vertex C?

4

200
What is a Path?
  • No edges repeated
  • No vertices repeated
200

With which group is Damon Albarn the lead singer?

Blur

200

Look at the network. What is the shortest distance from S to F?

25

300

What is a bridge? Draw an example of a connected graph that includes a bridge

A connected graph has every vertex connected to every other vertex, either directly or indirectly via other vertices.

The graph on the right is connected. A bridge is an edge in a connected graph that, if removed, will cause the graph to be disconnected.

300

Look at the graph. What is the sum of the vertices?

20

300

What is a circuit?

  • Type of Trail
  • Starts & ends at same vertex
  • Can’t repeat start/end vertex throughout trail
  • Other vertices may be repeated 
  • No edges repeated
300

What is the highest mountain in Victoria?

Mt Bogong

300

What is the name of the process used to find the shortest path between to points?

Dijkstra's algorithm

400

What is a complete graph? Draw an example

If there is an edge between every pair of vertices, the graph is called a complete graph. Every vertex in the graph is connected directly by an edge to every other vertex in the graph.

400

Look at the graph. Draw a subgraph that only involved vertices D, F and C

I have to write something here

400

What is a cycle?

  • Type of path
  • Starts & ends at same vertex
  • No other vertices repeated
  • No edges repeated
400
There are only three words in the English Language with three sets of double letters consequentially. Name one

Bookkeeper

Bookkeeping

Bookeepers

400

Look at the network. A power sub-station is be located at S. Find the minimum length of cable, in meters, needed to connect each point to the sub-station.

To do this you will use Prim's algorithm. In which order do you connect the points to the sub-station?

36 meters

S to A, A to B, B to C, B to E, E to G, G to H, H to D, G to F

500

What is an isomorphic graph? Draw an example

All of the graphs shown contain exactly the same information.

All of these graphs are considered to be equivalent to each other because they all contain identical information.

Each has edges connecting the same vertices.

500

A graph has 5 faces and 10 edges, how many vertices does it have?

7

500

What is the difference between an Eulerian trail and an Eulerian Circuit?

An Eulerian trail is a trail that follows every edge exactly once. Like other trails, vertices may be repeated.

An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex.


500

What country's name contains every vowel?

Mozambique 

500

George's friends offer to help with his birthday party.
Nathan offers to bring cake or balloons

Natalie offers to bring serviettes, cake or candles

Dianne offers to bring serviettes

Doug offers to bring serviettes or balloons.
Who should bring what?

Dianne - serviettes
Natalie - candles

Nathan - cake

Doug - balloons

M
e
n
u