Struktur Diskrit : Latihan Soal Model Graf, Jenis Graf, dan Implementasinya
1. Draw graph models, stating the type of graph used, to represent airline routes where every day there are
- four flights from Boston to Newark,
- two flights from Newark to Boston,
- three flights from Newark to Miami,
- two flights from Miami to Newark,
- one flight from Newark to Detroit,
- two flights from Detroit to Newark,
- three flights from Newark to Washington,
- two flights from Washington to Newark, and
- one flight from Washington to Miami
- an edge between vertices representing cities that have a flight between them (in either direction).
- an edge between vertices representing cities for each flight that operates between them (in either direction).
- an edge between vertices representing cities for each flight that operates between them (in either direction), plus a loop for a special sightseeing trip that takes off and lands in Miami.
- an edge from a vertex representing a city where a flight starts to the vertex representing the city where it ends.
- an edge for each flight from a vertex representing a city where the flight begins to the vertex representing the city where the flight ends.
2. Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops. Use your answers to determine the type of graph in this graph.
3. Construct a niche overlap graph for six species of birds, where the hermit thrush competes with the robin and with the blue jay, the robin also competes with the mockingbird, the mockingbird also competes with the blue jay, and the nuthatch competes with the hairy woodpecker.
4. In a round-robin tournament the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles, and the Cardinals beat the Orioles. Model this outcome with a directed graph.
5. Construct an influence graph for the board members of a company if the President can influence the Director of Research and Development, the Director of Marketing, and the Director of Operations; the Director of Research and Development can influence the Director of Operations; the Director of Marketing can influence the Director of Operations; and no one can influence, or be influenced by, the Chief Financial Officer
6. Construct a precedence graph for the following program :
- S1: x := 0
- S2: x := x + 1
- S3: y := 2
- S4: z := y
- S5: x := x + 2
- S6: y := x + z
- S7: z := 4
7. For each course at a university, there may be one or more other courses that are its prerequisites. How can a graph be used to model these courses and which courses are prerequisites for which courses? Should edges be directed or undirected? Looking at the graph model, how can we find courses that do not have any prerequisites and how can we find courses that are not the prerequisite for any other courses?
8. The intersection graph of a collection of sets A1, A2,...,An is the graph that has a vertex for each of these sets and has an edge connecting the vertices representing two sets if these sets have a nonempty intersection. Construct the intersection graph of these collections of sets.
9. Describe a graph model that represents traditional marriages between men and women. Does this graph have any special properties?
10. Describe a graph model that represents the positive recommendations of movie critics, using vertices to represent both these critics and all movies that are currently being shown.
Sumber
Slide Strukdis : Exercise 2
Posting Komentar