Explain what we need change to make the following network simple:
State whether the following networks are simple:
The social network Bleeter allows people to share content (in the form of "Bleets") online.
Before anyone can share anything, two people must first make a connection, so one person "follows" the other. Whenever a person creates a Bleet, it is shared with everyone who follows them. These people are called "followers".
The given network represents the connections among a group of six users of Bleeter. An arrow from one vertex to another means that the first person follows the second. So DF follows BK.
What kind of network, directed or undirected, represents the connections people form on Bleeter?
Which user has the most followers?
Which user follows the most people?
Is this an example of a simple network? Explain your answer.
Consider the table below:
For each number of vertices in the first row of the table, draw a simple network and then fill in the number of edges in the resulting network in the second row of the table:
| Vertices | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| Edges |
Determine the rule that calculates the number of edges, E, given the number of vertices, V, for a simple network.
Hence calculate the number of edges required for a simple network with 10 vertices.
Define the following in terms of graph theory:
A connected graph
A bridge
Consider the following graph:
Which vertex is isolated?
How many edges are there?
How many vertices are there?
Which vertex is the loop connected to?
Is the graph simple? Explain your answer.
Is the graph connected? Explain your answer.
Determine whether the following statements are true or false in relation to undirected connected graphs:
There is an isolated vertex.
There are no loops.
Each vertex is linked to another vertex only through one edge.
Every vertex is reachable via some path from every other vertex.
State whether the following graphs are connected:
Consider the given disconnected network:
In order to make the network connected, an edge from vertex P chould be drawn to which other vertices?
If edge WU is added, will there be a path from P to Q?
Consider the given disconnected directed network:
In order to make the network connected, an edge from vertex P could be drawn to which other vertex?
After adding this edge, is there now a path from R to P?
Consider the following diagram:
State the number of vertices.
State the number of edges.
Copy and complete the following table:
| Vertex | A | B | C | D | E |
|---|---|---|---|---|---|
| Degree |
Is the graph connected or disconnected?
Consider the following diagram:
State the number of vertices.
State the number of edges.
Describe the graph as connected or disconnected.
Complete the table below:
| Vertex | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| Degree |
For the following pairs of graphs, determine whether Graph 2 is a subgraph of Graph 1:
Graph 1
Graph 2
Graph 1
Graph 2
Graph 1
Graph 2
Find the weight of each highlighted subgraph:
Consider the given graph:
Find the weight of the subgraph formed by the vertices P, S, and V.
Find the weight of the subgraph formed by deleting vertices V, W, T, and S, along with all connecting edges.
Define the term "bipartite graph".
State whether the following graphs are bipartite graphs:
Define the term "complete graph".
State whether the following graphs are complete graphs:
Determine the number of edges in a complete graph which has:
3 vertices
4 vertices
5 vertices
n vertices
Determine the number of vertices in a complete graph which has 6 edges.
A complete bipartite graph is a special kind of bipartite graph where every vertex of the one group is connected to every vertex of the other group. State whether the following are complete bipartite graphs:
Determine the number of edges in a complete bipartite graph which has:
2 vertices in each group.
3 vertices in each group.
4 vertices in each group.
n vertices in each group.
Write down the terms that describe each of the following graphs from the list of terms below:
Complete
Connected
Simple
Directed
Bipartite
Weighted
