Easy graph theory question: maximise sum of visited nodes

In summary, the conversation is about finding the largest sum that can be made by adding up numbers while moving from the bottom left corner to the top right corner of a grid. The problem is from an intro to computer science course and the person asking for help has already figured out the answer but is interested in seeing different methods to solve it.
  • #1
hallwayantics
6
0

Homework Statement



Starting in the bottom left corner and moving either up or right, one square at a time, adding up the numbers along the way, what is the largest sum that can be made once you have reached the top right corner


142212
431343
214212
122331
413121
314342
211113
342322
This is from an "intro to computer science" course. My prof was a bit of a lazy bastard and just threw these random technical questions into the mix with the knowledge questions without giving us homework solutions or anything you could call teaching beyond, "it's just graph theory" in class.

Homework Equations


The Attempt at a Solution

no idea.
Thanks for looking.
 
Last edited:
Physics news on Phys.org
  • #2
I actually figured out the answer but I'm still interested in seeing what methods people will use to solve this problem.
 

Related to Easy graph theory question: maximise sum of visited nodes

1. What is graph theory?

Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model pairwise relations between objects. These objects are represented as nodes or vertices, and the relations are represented as edges.

2. How do you define "visited nodes" in a graph?

In this context, "visited nodes" refers to the nodes that have been traversed or explored during a certain process, such as finding the shortest path or maximizing a sum. These nodes are marked or labeled as visited to avoid revisiting them and to keep track of the progress.

3. What does it mean to maximize the sum of visited nodes?

To maximize the sum of visited nodes means to find a path or combination of nodes that results in the highest possible sum of their values. In other words, it is finding the most efficient way to move through the graph and selecting the nodes with the highest values in order to achieve the maximum sum.

4. Is it always possible to maximize the sum of visited nodes in a graph?

No, it is not always possible to maximize the sum of visited nodes in a graph. It depends on the structure of the graph and the values assigned to the nodes. In some cases, there may not be a path that allows for the maximum sum to be achieved.

5. What are some common algorithms used for maximizing the sum of visited nodes in a graph?

Some common algorithms used for this purpose include Depth-First Search (DFS), Breadth-First Search (BFS), and Dijkstra's algorithm. These algorithms use different approaches to explore the graph and find the path with the highest sum of visited nodes.

Similar threads

Teachers: Complex Intellectuals with Simple Emotional Needs
    • STEM Educators and Teaching
2
Replies
58
Views
9K
Mathematica This Week's Finds in Mathematical Physics (Week 262)
    • MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top