graphs (union, intersection,

[mm12463]

First I'll start out with this is not a homework assignment.

So we are going over graphs and I am trying to understand where some of this is used in computer programming. Keep in mind this is non-visual.

This is basica algebra.

Intersection is when two sets of data (elements of the set) containing some data that is both sets.
Example
Set A = {10,20,30,40}
Set B = {11,20,30,51}

In this case the numbers 20 and 30 are in both sets. Therefore these two sets intersect.

This is also an example of union. In a union all the data (or elements of the sets) that are in Set A and Set B. So all the numbers 10,11,20,30,40,51 belong to this union.

What I am trying to understand is how is this used in a non visual program. I know the book says it is used for project managment, electrical circuits but really does not go into how or show what you use it for when you use graphs and use intersection, subsets, union, etc, etc.

Just elements to me. Could be used for a lot things in a program or maybe I am look at this wrong.

BTW - the homework is outputting the nodes of a graph in a depth first traveral.

Thank you very much.

[Eri523]

Though you have the word "graphs" is your thread title, your question actually seems to rather be about sets. And, funnily, just right now I'm working on a real-life program where they do a good job for me. However, perhaps it's rather abstract to explain the practical use of sets of integers, and in my program it actually are sets of strings.

Say you want to track changes of the inventory of files in a certain domain (say a certain disk directory, though it's somewhat more complex in the real app). Now I have a list of names of files that have been there at a certain earlier point in time and a list of files that are there right now. I put both the lists into a set of strings (std::set<std::string>) each.

Now the intersection of the two sets contains the files that have been there before and are still there (though their content may have chaged; we're just checking the names), and the union of the sets contains the files that have been there before and/or are there now (rather uninteresing in practice, IMO). What really interests me here, though, are the two asymmetric set differences (AKA relative complement, in C++ determined using std::set_difference()): One contains the files that have been there but have been deleted now, and the other one contains the files that are new, and these are the two sets of files I need to process further in my program. (For completeness note that, in this model, files that have been renamed in the meantime will show up in both the "deleted" an "new" sets under different names, and from the data we're considering here there's no way to know that it's actually the same file under different names. That's not a problem in my real-life app, though.)

[nuzzle]

Could be used for a lot things in a program or maybe I am look at this wrong.

Sure, you're free to use set theory for anything you like, just as you're free to count anything you like using natural numbers.

[mm12463]

The chapter is on Graphs and understand graph theory, how we represent graphs in memory, impletenting graph algorithms, shortest path algorithms. It just confusing.

I understand what you are saying about the files being in the same set. The logic there makes sense to me. '

But how unions and sets and basically the entire graph theory has me really lost. We had one example a friend had and he was mention if we know the weighted paths of nth vertices in a graph for say a bus route around the city. Edges, vertices. UGH! lol

Maybe I didn't ask this questions correction or explain it very well. Just a very confusing chapter for me. Yah sets makes sense to me. But how it applies to the graphs is different in a way least my head. I just see it as 2 numbers in a set. Guess the numbers in a set in graphs is basically the "coordinates". Vertice in Graph has a set of (1,2), (1,4),(3,1) (3,4) where it is basiicaly saying 1 to 2 is has an edge, 1 to 4, 3,1 and 3 to 4 and each number is a vertice of the graph.

I don't know. Just hard to think of it as a graph. THink that is my road block.


But I thank you for trying to help me out. I think this will end up being a trip to the tutor and go through the chapter and have him explain it better.

[Lindley]

Guess the numbers in a set in graphs is basically the "coordinates". Vertice in Graph has a set of (1,2), (1,4),(3,1) (3,4) where it is basiicaly saying 1 to 2 is has an edge, 1 to 4, 3,1 and 3 to 4 and each number is a vertice of the graph.

That's basically correct.

I don't know. Just hard to think of it as a graph. THink that is my road block.

The word "graph" is a bit overloaded in mathematics. You probably think of a graph as a plot of x versus y for some function. This usage of the word is completely different. (I'm sure there's a link on some level, but it's conceptually easier to start from scratch.)

A graph is a collection of vertices (singular vertex; the plural vertexes is sometimes used instead) connected by directed or undirected edges. Graphs can be represented visually but they don't have to be drawn in order to be a graph.

One example of a well-known graph algorithm is Google Maps. Every intersection on the map is a vertex; roads form edges between them. Then when you put in a starting point and destination, Google Maps uses a graph algorithm (probably Dijkstra) to compute the shortest path between those two points.

[monarch_dodra]

Also a "set" is just a simplified version of a graph: It is basically just a bag with the elements (vertexes), but without the connectors (edges).

Here is a practical example:

A map of North America.
It is a graph.
-The cities are the vertexes
-The roads are the edges

Now imagine you have both a map of North America, and of Latin America, and you only care about the cities, and not the roads: That is a set.

The intersection of North America and Latin America is... Mexico!
The union of North America and Latin America is... The Americas!
In simplified geography anyways

Maybe that helps?

[Lindley]

Graphs can also be used to solve the "map coloring problem". Consider a map of the United States. You wish to draw each state in a different color such that no adjacent states are the same color.

To do this, you can represent each state as a vertex, and states sharing a common border have an edge between them. Then you run a graph coloring algorithm to assign colors to each vertex with no edge connecting two vertices of the same color.